Advanced Data Structures - Java Concepts - page 1017

reversing all comparisons in the heap-building algorithm. If there is a possibility of
misunderstanding, it is best to refer to the data structures as min-heap or max-heap.
The test program demonstrates how to use a min-heap as a priority queue.
ch16/pqueue/MinHeap.java
1 import java.util.*;
2
3 /**
4 This class implements a heap.
5 */
6 public class MinHeap
7 {
8 /**
9 Constructs an empty heap.
10 */
11 public MinHeap()
12 {
13 elements = new ArrayList<Comparable>();
14 elements.add( null );
15 }
16
17 /**
18 Adds a new element to this heap.
19 @param newElement the element to add
20 */
21 public void add(Comparable newElement)
22 {
23 // Add a new leaf
24 elements.add( null );
25 int index = elements.size() - 1 ;
26
27 // Demote parents that are larger than the new element
28 while (index > 1
29 &&
getParent(index).compareTo(newElement) > 0 )
30 {
31 elements.set(index,
getParent(index));
32 index = getParentIndex(index);