Assignment 04
Implementing a binary heap and priority queue
Overview
In this lab, you will implement a new ADT, the priority queue. Like a standard queue, a priority queue allows a user to add and remove elements from a collection. Unlike a standard queue, a priority queue allows the user to specify a priority for each element when it is added. The removal method then returns and removes the element with the highest priority.
In this lab you will provide an implementation of a priority queue using a heap data structure. A heap is type of binary tree where each node stores an element that is smaller than the values stored by its children. Moreover, heaps are always “complete” binary trees, hence they are wellbalanced. This feature of heaps allows for very efficient addition and removal of elements (so long as only the smallest element is ever removed). You will demonstrate this efficiency by comparing the performance of your heapbased priority queue implementation to a (provided) AVL tree implementation.
Background
Priority Queues
A priority queue is a container of elements where each element has an associated priority. (You may assume that priorities of elements are distinct, so that given any pair of elements, one has strictly higher priority than the other.) More formally, the state of a priority queue can be represented as a set of pairs:
\[S = \{(k_0, x_0), (k_1, x_1), \ldots, (k_{n1}, x_{n1})\}\]where each \(x_i\) is an element in the queue and \(k_i\) is an integer representing \(x_i\)’s priority. We assume that smaller numbers indicated higher priority: an elment with priority \(1\) has higher priority than an element with priority \(2\), and so on. In the state \(S\) depicted above, we assume \(k_0 < k_1 < \cdots < k_{n1}\) so that \(x_0\) has the highest priority, etc.
In addition to the usual \(\mathrm{size}()\) and \(\mathrm{isEmpty}()\) methods, priority queues offer the following methods:

\(\mathrm{min}()\) returns the element with highest priority in the queue. For the state \(S\) as above, the element \(x_0\) is returend.

\(\mathrm{insert}(k, x)\) insert element \(x\) into the queue with priority \(k\). If \(k\) satisfies \(k_i < k < k_{i+1}\), then after this operation, the state is updated to
\[S = \{(k_0, x_0),\ldots, (k_i, x_i), (k, x), (k_{i+1}, x_{i+1}),\ldots, (k_{n1}, x_{n1}).\}\] 
\(\mathrm{removeMin}()\) remove and return the element with highest priority in the queue. This operation updates the state to
\[S = \{(k_1, x_1), \ldots, (k_{n1}, x_{n1})\}\]and returns the value \(x_0\).
See SimplePriorityQueue.java
for a specification of a Java interface for the priority queue ADT.
Heaps
A (binary) heap is a data structure that stores comparable elements—i.e., for any two distinct elements, one can be said to be larger than the other according to some “natural ordering.” A heap can be represented as binary trees, where each node stores a value that is larger than the node’s childrens’ values. Heaps are, in some sense, maximally balanced, as they are always “complete” binary trees. Here, a complete binary tree of depth \(d\) is a binary tree with the following properties:

All nodes at depth \(d' \leq d  2\) have two children.

At most one node at depth \(d  1\) has one child, and that is its left child.

If \(v\) is a node at depth \(d  1\) with a (left) child and \(u\) is also at depth \(d  1\) to the left of \(v\), then \(u\) has two children.
These properties allow us to store complete binary trees (hence heaps) efficiently in arrays (rather than linked nodes as we previously used for binary search trees). Further, adding to and removing the smallest element from a heap can be peroformed efficiently (in \(O(\log n)\) operations for a heap of \(n\) elements).
You can read about array representations of binary heaps in ODS Section 10.1. The linked reference will give a complete description of the procedures for adding to and removing from binary heaps.
Given the efficiency of adding to a heap and removing its smallest element, the heap is a natural data structure to implement a priority queue. To do this, one can define a Pair
datatype that stores an element together with its priority: \((k, x)\). Two Pair
s can be compared as follows: \((k, x) < (k', x')\) whenever \(k < k'\). Under this ordering, the smallest pair \((k, x)\) stored in the heap contains the highest priority element (\(x\)) in the queue.
Your Task
For this assignment, you will implement a heap called ArrayBinaryHeap
. Your heap must use an array to store its contents, and implement the methods described above in the manner described in class (see also here). You will then use teh ArrayBinaryHeap
to implement a SimplePriorityQueue
(code provided), and test its performance against an implementation using an AVL tree.
Code
Complete code: hw04.zip

ArrayBinaryHeap.java
gives scaffolding for your binary heap implementation. Note that this program only gives the minimal methods needed to compile and run the tester—you will almost certainly want to add some of your own methods as well! 
SimplePriorityQueue.java
specifies a priority queue interface. 
HeapPriorityQueue.java
provides aSimplePriorityQueue
implementation, given theArrayBinaryHeap
implementation. 
PriorityQueueTester.java
tests your priority queue (hence heap) implementation for correctness. AVLTree.java
provides an AVL tree implementation against which you can test the performance of your heap. You’ll also need the following files:AVLPriorityQueue.java
provides a priority queue implementation using the providedAVLTree
to store elements. Compare the performance of yourHeapPriorityQueue
with this.
Questions

Write a program that compares the performance (i.e., empirical running time) of your heapbased priority queue and the provided
AVLTree
implementation. Be sure to test both theinsert
andremoveMin
methods. How do the running times scale with the size of the data structure for the two implementations? How do the running times for the two implementations compare to each other? 
Suppose you wanted to supplement your
ArrayBinaryHeap
with a method to search for a given element in the heap (like thefind
method forSimpleSSet
). Without modifying the heap structure (and insert/remove methods), is it possible to search for a given element significantly faster than traversing the entire array? Why or why not?
What to Submit
ArrayBinaryHeap.java
containing your binary heap implementationresponse.md
containing your responses to the questions above
Evaluation
Your submission will receive a score out of 10 points, broken down as follows:
 5 points for
ArrayBinaryHeap.java
 code compiles, runs, and passes tests in
PriorityQueueTester.java
 code implements a heap as specified
 code is wellorganized and documented with comments
 code compiles, runs, and passes tests in
 5 points for responses to the questions above