Assignment 07: Binary Heap Priority Queue

Implementing a binary heap and priority queue

Overview

In this lab, you will implement 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 well-balanced. 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 heap-based 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_{n-1}, x_{n-1})\}\]

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_{n-1}\) 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_{n-1}, x_{n-1}).\}\]

  • \(\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_{n-1}, x_{n-1})\}\]

    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:

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

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

  3. 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 Pairs 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). Specifically, your implementation should use an array to store the elements of the heap. The elements in the heap can be of any type implementing the Comparable interface. You should complete the following class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class ArrayBinaryHeap<E extends Comparable<E>> {

    ...
	
    public int size() {...}
	
    public boolean isEmpty() {...}

    public E min() {...}

    public E removeMin() {...}

    public void insert(E x) {...}
}

Once you’ve completed ArrayBinaryHeap, the provided HeapPriorityQueue.java uses your ArrayBinaryHeap to implement the SimplePriorityQueue interface. You will then test the performance of the HeapPriorityQueue against the (provided) AVLPriorityQueue, which uses an AVL tree to implement a priority queue.

Code

Complete code: hw07-heap-priority-queue.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 a SimplePriorityQueue implementation, given the ArrayBinaryHeap 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 provided AVLTree to store elements. Compare the performance of your HeapPriorityQueue with this.

Questions

  1. Write a program that compares the performance (i.e., empirical running time) of your heap-based priority queue and the provided AVLTree implementation. Be sure to test both the insert and removeMin 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?

  2. Suppose you wanted to supplement your ArrayBinaryHeap with a method to search for a given element in the heap (like the find method for SimpleSSet). 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 implementation
  • response.pdf 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 well-organized and documented with comments
  • 5 points for responses to the questions above