teaching machines

CS 245 Lecture 27 – Heap Implementation

December 10, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

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?

1. 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);

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

  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