Heap Demonstration

Dusty Phillips
Athabasca University
May 25, 2004
Last updated Jun 7, 2004

This applet visually demonstrates the use of Heaps in programming. View the applet in the Applet section below. The usage of the applet is described in the following Usage section. For those interested, the Display and design of the applet are also described.

Applet

Usage

Usage of the heap applet is quite simple. You will be presented with an empty heap (maximum size: 15) and will have the option to Insert an element into the heap. You will first be prompted for an item to input. If it is a valid Integer, it will be inserted into the heap.

Your other option is to RemoveMax the maximum element. This will remove the element in question, and will then illustrate the process of sifting a new maximum into the heap.

This demonstration does not show the process of building a heap if all elements are available in advance.

This demonstration assumes you have a general idea of how a maxheap or priority queue is implemented, as the complete binary tree array is somewhat confusing.

Display

The display will be divided into three areas. The Upper input area will have high-level buttons for Inserting elements and removing the maximum element (RemoveMax), as well as stepping through the code and resetting the applet.

A lower left processing area will contain an overview of the data type class (including instance variables and methods), as well as a second Pseudocode area for a particular method currently being executed.

A larger visualization area will be displayed to the right. This area will visually display the heap in two different views. The first view will display the heap array (array implementation for complete binary trees is common). The second will show a logical view of the heap. The two will be coordinated by showing the array index as well as the value with the logical view of the heap. When operations are performed on the heap, the heap elements in question will be highlighted in both views. When heap elements are swapped, they will flash in the tree view. The more important element is highlighted in red, while the element being compared is highlighted in green.

Design

The design will be similar to the previous demonstrations. There will be a ProgramPanel to hold the main Pseudocode, and separate Pseudocodes for the two buttons. In addition, there will be a Pseudocode for the private sifdown() method.

There will be a single HeapPanel that contains the two views of the heap. This will have methods to manipulate the heap itself as well as the display. There will be separate panels for each of the displays; HeapPanel will forward instructions to each of these. They will share a common heap stored in the HeapPanel.

The main Pseudocode: class Heap { private int maxsize = 15 private int[] heap = new int[maxsize] private int n public void insert(int val); public int removemax(); private void siftdown(int pos); private void swap(int i, int j); private void leftchild(int pos); private void rightchild(int pos); private void parent(int pos); private void isLeaf(int pos); }

The insert() Pseudocode: public void insert(int val) { if (n == size) throw HeapFullException int curr = n n++ heap[curr] = val while (curr != 0 && heap[curr] > heap[parent(curr)]) { swap(curr, parent(curr)) curr = parent } }

The removeMax() Pseudocode: public int removemax() { if (n == 0) throw EmptyHeapException n-- swap(0, n) if (n != 0) siftdown(0) return heap[n] }

The siftdown() Pseudocode: private void siftdown(int pos) { while (!isleaf(pos)) { int j = leftChild(pos) if (j < n-1 && heap[j] < heap[rightChild(pos)]) j = rightChild(pos) if (heap[pos] >= heap[j]) return swap(pos, j) pos = j } }