# teaching machines

## 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
• remove

### What Does This Do?

1. String s = "5 7 9 3 11 2";
Scanner in = new Scanner(s);
MinHeap<Integer> heap = new MinHeap<Integer>();

while (in.hasNextInt()) {
}

ArrayList<Integer> numbers = new ArrayList<Integer>();
while (heap.size() > 3) {
}

System.out.println(numbers);

2. 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();
}

// blindly add newItem to end of list
// then reheap upward from that point
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>();
System.out.println(heap);
}