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?

  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

One shining moment
I was above all others
But lo, first can’t last

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *