CS 245 Lecture 27 – Heap Implementation
Agenda
- what ?s
- data structure utility belt
- what does this do?
- implementing a heap
- using an ArrayList
- size
- isEmpty
- clear
- finding children of a parent and parent of a child
- add
- remove
What Does This Do?
String s = "5 7 9 3 11 2"; Scanner in = new Scanner(s); MinHeap<Integer> heap = new MinHeap<Integer>(); while (in.hasNextInt()) { heap.add(in.nextInt()); } ArrayList<Integer> numbers = new ArrayList<Integer>(); while (heap.size() > 3) { numbers.add(heap.remove()); } System.out.println(numbers);public <T> T foo(MaxHeap<T> heap, int n) { for (int i = 0; i < n - 1; ++i) { heap.remove(); } return heap.remove(); }
Code
Heap.java
package lecture26;
import java.util.ArrayList;
public class Heap<T extends Comparable<T>> {
private ArrayList<T> items;
public Heap() {
items = new ArrayList<T>();
}
public int size() {
return items.size();
}
public boolean isEmpty() {
return items.isEmpty();
}
public void clear() {
items.clear();
}
public void add(T newItem) {
// blindly add newItem to end of list
// then reheap upward from that point
items.add(newItem);
reheapUp(size() - 1);
}
public String toString() {
return items.toString();
}
public T get(int i) {
return items.get(i);
}
private void reheapUp(int startingAt) {
T newItem = get(startingAt);
int iChild = startingAt;
int iParent = (iChild - 1) / 2;
// Reheap up as long as newItem < parent AND hay un padre
// As long as there's a parent and the newItem is greater than the parent,
// let's move that parent down the tree. Then, let's move up to the next
// level.
while (iChild > 0 && newItem.compareTo(get(iParent)) > 0) {
items.set(iChild, get(iParent));
iChild = iParent;
iParent = (iChild - 1) / 2;
}
// Finally, the newItem can be inserted.
items.set(iChild, newItem);
// compare newItem to possible parent
// if newItem > parent
// put parent in child's spot
// move up a level
}
public T remove() {
return null;
}
public static void main(String[] args) {
Heap<Integer> heap = new Heap<Integer>();
heap.add(6);
System.out.println(heap);
heap.add(7);
System.out.println(heap);
heap.add(8);
System.out.println(heap);
}
}
Haiku
One shining moment
I was above all others
But lo, first can’t last
I was above all others
But lo, first can’t last