Dusty Phillips

Athabasca University

May 25, 2004

Last updated Jun 7, 2004

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.

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.

The display will be divided into three areas. The Upper
input

area will have high-level buttons for
**Insert**ing 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.

The design will be similar to the previous demonstrations.
There will be a `ProgramPanel`

to hold the
main `Pseudocode`

, and separate `Pseudocode`

s
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
}
}
```