Page 208 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

Figure 10.2: Object Class Hierarchy Notes
Comparable Abstract Object
Container Abstract Container
PriorityQueue BinaryHeap
MergeablePriorityQueue BinomialQueue
Tree LeflistHeap
AbstractTree BinaryTree
GeneralTree BinomialTree

Program-10.1 Introduces the BinaryHeap class. The BinaryHeap class extends the
AbstractContainer class introduced in Program 10.1 and it implements the PriorityQueue
interface defined in Program 10.1.

public class BinaryHeap
extends AbstractContainer
implements PriorityQueue
{
protected Comparable [] array;
// ...
}

Program 10.1: BinaryHeap Fields

10.2.3 Putting items into a Binary Heap

There are two requirements which must be satisfied when an item is inserted in a binary heap.

First, the resulting tree must have the correct shape. Second, the tree must remain heap-ordered.
Figure 10.3 illustrates the way in which this is done.
Since the resulting tree must be a complete tree, there is only one place in the tree where a node can

be added. That is, since the bottom level must be filled from left to right, the node node must be
added at the next available position in the bottom level of the tree as shown in Figure 10.3 (a).
Figure 10.3: Inserting an item into a Binary Heap

LOVELY PROFESSIONAL UNIVERSITY 203