Lab 15: Building a Heap

In this lab you will create a heap. To decrease the amount of code you will write, we will not follow the book exactly (though you are free to do so if you want), and code the binary tree structure directly in the heap instead of having a separate class that implements a complete binary tree.

You should use the following class to store an element in the heap:

public class Entry<K extends Comparable<K>, V> {
  private K key;
  private V value;
  
  public Entry(K key, V value) {
    this.key = key;
    this.value = value;
  }
  
  public K getKey() {
    return key;
  }
  
  public V getValue() {
    return value;
  }
}
Now create the class Heap<K extends Comparable<K>, V>. The heap should contain an array of Object to implement the heap. The constructor is:
  1. Heap(int size):
    Allocates a heap of the given size.
The necessary methods are:
  1. private int leftChild(int node):
    Returns the index of the left child of the node index.
  2. private int rightChild(int node):
    Returns the index of the right child of the node index.
  3. private int parent(int node):
    Returns the index of the parent of the node index.
  4. private boolean isRoot(int node):
    Returns true if the heap element indexed by node is the root node.
  5. private boolean hasRightChild(int node):
    Returns true if the heap element indexed by node has a right child.
  6. private boolean hasLeftChild(int node):
    Returns true if the heap element indexed by node has a left child.
  7. private boolean isLeaf(int node):
    Returns true if the heap element indexed by node is a leaf node.
  8. private K getKey(int node):
    Returns the key of the element at index node.
  9. private void bubbleUp(int node):
    Bubble the element at index node up the heap. Use the helper methods you wrote above to assist you.
  10. private void bubbleDown(int node):
    Bubble the element at index node down the heap. Use the helper methods you wrote above to assist you.
Finally the public methods:
  1. public boolean isEmpty():
    Returns true if the heap is empty.
  2. public void insert(K key, V value):
    Insert the element value into the heap with priority key.
  3. public Entry<K,V> removeMin() throws HeapEmptyException:
    Remove the element with greatest priority (i.e. least key).
Do not worry about the event that someone tries to insert into a full heap. Later you can implement a routine that doubles the array size in that event. At the end of the lab, email what you have to your instructor, hsc@albion.edu.