A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 814

implementation of the
basic operations

21.2

The heap-order property looks promising so far because easy access to the
minimum is provided. We must now show that we can efficiently support
insertion and deleteMin in logarithmic time. Performing the two required
operations is easy (both conceptually and practically): The work merely
involves ensuring that the heap-order property is maintained.

21.2.1 insertion

To insert an element X in the heap, we must first add a node to the tree. The
only option is to create a hole in the next available location; otherwise, the
tree is not complete and we would violate the structure property. If X can be
placed in the hole without violating heap order, we do so and are done. Other-
wise, we slide the element that is in the hole's parent node into the node, bub-
bling the hole up toward the root. We continue this process until X can be
placed in the hole. Figure 21.7 shows that to insert 14, we create a hole in the
next available heap location. Inserting 14 into the hole would violate the heap-
order property, so 31 is slid down into the hole. This strategy is continued in
Figure 21.8 until the correct location for 14 is found.
This general strategy is called percolate up, in which insertion is imple-
mented by creating a hole at the next available location and bubbling it up the
heap until the correct location is found. Figure 21.9 shows the add method,
which implements the percolate up strategy by using a very tight loop. At
line 13, we place x as the - ∞ sentinel in position 0. The statement at line 12
increments the current size and sets the hole to the newly added node. We
iterate the loop at line 15 as long as the item in the parent node is larger than x .

Insertion is imple-
mented by creating
a hole at the next
available location
and then percolat-
ing it up until the
new item can be
placed in it without
introducing a heap-
order violation with
the hole's parent.

figure 21.7
Attempt to insert 14,
creating the hole and
bubbling the hole up

14 13 13

21 16 21 16

24 24

31 19 68 19 68

65 26 32 65 26 32 31

(a) (b)