Algorithms Tick 1: binary heap

The heap is a fundamental data structure. You have already met the binary heap and seen it used for Heapsort. Later in the course you will see other heap implementations, including the binomial heap and the Fibonacci heap, and you will see how heaps are used for graph algorithms.

In this tick, you will implement a binary max-heap (i.e. each node’s value is ≥ those of its children). Your implementation should follow the algorithm described in lecture notes section 2.12, which has \(O(n)\) heap construction and \(O(\log n)\) extraction.

Submission (Python)

Submission filename: maxheap.py

Please submit a source file maxheap.py that implements three functions:

# rearranges the list x so that it satisfies the heap property
heapify(x)

# insert a new element e into the heap x
push(x, e)

# update the heap x by removing its maximum element, and return that element;
# or raise IndexError if x is an empty list
popmax(x)

Note: The Python standard library defines a function heapq.heapify(x) that rearranges an unsorted list into a heap. For this tick, you have to implement it yourself, without using the standard library! Note also that in lecture notes section 2.12, we defined a different function heapify(a, iEnd, iRoot) that converts an almost-heap into a heap.

Submission (Java)

Submission filename: MaxCharHeap.java

Please create a class MaxCharHeap that has a constructor with the signature

// create a new binary max-heap (without modifying x)
public MaxCharHeap (char[] x);

and that implements the interface uk.ac.cam.cl.tester.Algorithms.MaxCharHeapInterface:

package uk.ac.cam.cl.tester.Algorithms;

public interface MaxCharHeapInterface {
    // insert a new value e into the heap
    public void insert(char e);
    // get and remove the maximum value (or throw an exception if empty)    
    public char popMax() throws EmptyHeapException;
    // get the number of items in the heap
    public int getLength();
}

The exception EmptyHeapException (also in uk.ac.cam.cl.tester.Algorithms) should be thrown whenever the user tries to extract from an empty heap.

The underlying storage in your heap should be a plain char[] array that expands as necessary to hold the heap. In your constructor you should create your own char[] array; treat as immutable the x that is passed in when calling the constructor. To expand an array you need to create a new one that is bigger and then copy across the old values and update the reference. e.g.

int[] myarray = new int[]{1,2,3,4};
// new bigger array    
int[] biggerarray = new int[5];
// copy
for (int i=0; i<myarray.size(); i++)
    biggerarray[i] = myarray[i];
// switch references
myarray = biggerarray;

If you dislike the \(O(n)\) cost associated with this, an alternative approach is to double the size of the array whenever it fills up. This gives amortised \(O(1)\) insertion, but is fiddlier to code since you need to keep track of the allocated array size as well as the number of used slots (a.k.a. the heap size). Both the \(O(n)\) and amortised \(O(1)\) approaches are acceptable for this tick.