TOC PREV NEXT

Program — Heap exercises

Goals

A priority queue is a data type whose elements each have a numeric priority. It supports the operations of

A binary heap implements a priority queue using an array, so that both the insertion and the removal operations in the worst case can be done in time proportional to the log of the number of elements in the queue.

For this assignment, you will implement a heap as a linked structure instead of using an array. We hope this will reinforce your understanding of heap operations and the features of an array that support their efficient implementation.

Related quizzes

Heaps.

Readings

Weiss (either edition), chapter 21.

Problem

Do the exercise described below.

Heap exercise

Code that implements a priority queue of int values as a binary max heap is given on the following pages, and is supplied in ~cs47b/lib/Heap.java.

Modify the implementation so that it no longer uses an array (or Vector, or any other contiguous storage). Instead, your implementation should use explicitly linked heap nodes and must implement all the public operations (constructor, isEmpty, remove, top, add, and display) provided by the array version. The add and remove operations in your revised implementation should still run in time proportional in the worst case to the log of the number of queue elements. The constructor and the isEmpty and top operations should run in constant time.

Your program tests should include the following sequence, initialized with a heap of at least six elements:

adding an element that fills the bottom level of the heap;
adding one more element, which will create a new bottom level;
removing an element from the heap;
removing one more element from the heap (this should restore the heap to where it was just after initialization);
adding two more elements, and doing two more removes.

Tutors will also ask you to verify that, for a heap containing n elements, your add and remove operations indeed can always be performed in log n time. Note that a complete binary tree with n nodes has n/2 leaves, so any operation that requires a search of a level of the tree isn't running quickly enough.

Checklist

Heap.java 

import java.util.*;

public class Heap {

	private final boolean DEBUGGING = true;
	private int mySize;
	private int [ ] myElements;
	
	// Maintain a binary max heap of ints that contains mySize elements. 
	// The entries of the heap are stored sequentially in the myElements array; 
	// thus the array represents a binary tree of mySize nodes whose depth is minimal 
	// and in which the bottom level is as far "left" as possible.  The parent of the entry 
	// at position k is at position (k-1)/2; the two children are at positions 2*k+1 and 2*k+2. 
	// Each entry in the heap has at least as large a value as its children.
	// Initialize an empty heap to hold up to the given number of elements.
	public Heap (int capacity) {
		mySize = 0;
		myElements = new int [capacity];
		if (DEBUGGING) {
			display ( );
			check ( );
		}
	}
	
	// Return true exactly when the heap is empty.
	public boolean isEmpty ( ) {
		return mySize == 0;
	}
	
	// Return the top of the heap.
	public int top ( ) throws NoSuchElementException {
		if (isEmpty ( )) {
			throw new NoSuchElementException ("accessing top of empty heap");
		}
		return myElements[0];
	}
	
	// Remove the top of the heap.
	public void remove ( ) throws NoSuchElementException {
		if (isEmpty ( )) {
			throw new NoSuchElementException ("removing from empty heap");
		}
		if (mySize == 1) {
			mySize = 0;
		} else {
			myElements[0] = myElements[mySize-1];
			mySize--;
			bubbleDown (0);
		}
		if (DEBUGGING) {
			display ( );
			check ( );
		}
	}
	
	// Add an element to the heap.
	public void add (int newElement) {
		myElements[mySize] = newElement;
		mySize++;
		bubbleUp (mySize-1);
		if (DEBUGGING) {
			display ( );
			check ( );
		}
	}
	
	// Move the heap entry indexed by k down the heap until it's larger than both its children.  
	// Each move exchanges the entry with its larger child.
	private void bubbleDown (int k) {
		assert (k >= 0 && k < mySize, "bubbling " + k + " down");
		while (2*k+1 < mySize-1) {
			int maxChildIndex = isGreater (2*k+1, 2*k+2)? 2*k+1: 2*k+2;
			if  (!isGreater (maxChildIndex, k)) {
				return;
			}
			exchange (maxChildIndex, k);
			k = maxChildIndex;
		}
		if (2*k+1 == mySize-1) {	/* maybe only one child */
			if (isGreater (mySize-1, k)) {
				exchange (mySize-1, k);
			}
		}
	}
	
	// Move the heap entry indexed by k up the heap until it's smaller than its parent.
	private void bubbleUp (int k) {
		assert (k >= 0 && k < mySize, "bubbling " + k + " up");
		while (k > 0 && isGreater (k, (k-1)/2)) {
			exchange (k, (k-1)/2);
			k = (k-1)/2;
		}
	}
	
	// Exchange the two heap elements at the given positions.
	private void exchange (int k1, int k2) {
		assert (k1 >= 0 && k2 >= 0 && k1 < mySize && k2 < mySize,
			"exchanging " + k1 + " with " + k2);
		int temp = myElements[k1];
		myElements[k1] = myElements[k2];
		myElements[k2] = temp;
	}
	
	// Return true exactly when the heap entry with index k1
	// is equal to heap entry with index k2.
	private boolean isEqual (int k1, int k2) {
		assert (k1 >= 0 && k2 >= 0 && k1 < mySize && k2 < mySize,
			"checking equality of " + k1 + " and " + k2);
		return myElements[k1] == myElements[k2];
	}
	
	// Return true exactly when the heap entry with index k1
	// is greater than the heap entry with index k2.
	private boolean isGreater (int k1, int k2) {
		assert (k1 >= 0 && k2 >= 0 && k1 < mySize && k2 < mySize,
			"comparing " + k1 + " and " + k2);
		return myElements[k1] > myElements[k2];
	}
	
	// Display the heap.
	public void display ( ) {
		System.out.println ("Heap (" + mySize + " elements):");
		displayHelper (0, 0);
		System.out.println ( );
	}
	
	// Display the subheap rooted at element k,
	// indenting each element according to the indent level argument.
	private void displayHelper (int k, int indentLevel) {
		if (k >= mySize) {
			return;
		}
		displayHelper (2*k+1, indentLevel+1);
		for (int j=0; j<indentLevel; j++) {
			System.out.print ("  ");
		}
		System.out.println (myElements[k]);
		displayHelper (2*k+2, indentLevel+1);
	}
	
	// Check the heap for consistency.
	// Each element must be at least as large as its children.
	private void check ( ) {
		int k;
		for (k=0; 2*k+1<mySize-1; k++) {
			assert (!isGreater(2*k+1,k), "checking left child of " + k);
			assert (!isGreater(2*k+2,k), "checking right child of " + k);
		}
		if (2*k+1 == mySize-1) {
			assert (!isGreater(2*k+1,k), "checking left (only) child of " + k);
		}
	}
	
	// Verify an assertion.
	private void assert (boolean whatIsAsserted, String condition) {
		if (!whatIsAsserted) {
			System.err.println ("Assertion failed while " + condition);
			throw new RuntimeException ( );
		}
	}
	
	public static void main (String [ ] args) {
		Heap h = new Heap (9);
		for (int i=1; ; i++) {
			try {
				h.add (i);
			} catch (Exception e) {
				System.out.println ("Heap filled up at insertion " + i);
				break;
			}
		}
		for (int i=1; ; i++) {
			try {
				h.remove ( );
			} catch (Exception e) {
				System.out.println ("Heap emptied at removal " + i);
				break;
			}
		}
		Random r = new Random ( );
		for (int i=1; ; i++) {
			try {
				int newElement = r.nextInt ( );
				newElement = newElement < 0? (-newElement)%10: newElement%10; 
				h.add (newElement);
			} catch (Exception e) {
				System.out.println ("Heap filled up at insertion " + i);
				break;
			}
		}
		for (int i=1; ; i++) {
			try {
				h.remove ( );
			} catch (Exception e) {
				System.out.println ("Heap emptied at removal " + i);
				break;
			}
		}
	}
}
TOC PREV NEXT