SORTING - Introduction to Java Programming: Comprehensive Version - page 876

Swap the current node with its parent;
Now the current node is one level up;
}

Suppose a heap is initially empty. That heap is shown in Figure 23.12, after adding numbers
3, 5, 1, 19, 11, and 22 in this order.

3 5 5

3 3 1

(a) After adding 3 (b) After adding 5 (c) After adding 1

19 19 22

5 1 11 1 11 19

3 3 5 3 5 1

(d) After adding 19 (e) After adding 11 (f) After adding 22

F IGURE 23.12

Elements 3, 5, 1, 19, 11, and 22 are inserted into the heap.

Now consider adding 88 into the heap. Place the new node 88 at the end of the tree, as shown
in Figure 23.13a. Swap 88 with 19, as shown in Figure 23.13b. Swap 88 with 22, as shown in
Figure 23.13c.

22 22 88

11 19 11 88 11 22

3 5 1 88 3 5 1 19 3 5 1 19

(a) Add 88 to a heap (b) After swapping 88 with 19 (c) After swapping 88 with 22

F IGURE 23.13

Rebuild the heap after adding a new node.

23.6.3 Removing the Root
Often you need to remove the maximum element, which is the root in a heap. After the root is
removed, the tree must be rebuilt to maintain the heap property. The algorithm for rebuilding
the tree can be described as follows:

Move the last node to replace the root;
Let the root be the current node;
while (the current node has children and the current node is
smaller than one of its children) {
Swap the current node with the larger of its children;
Now the current node is one level down;
}

Figure 23.14 shows the process of rebuilding a heap after the root 62 is removed from
Figure 23.11a. Move the last node, 9, to the root, as shown in Figure 23.14a. Swap 9 with 59,
as shown in Figure 23.14b; swap 9 with 44, as shown in Figure 23.14c; and swap 9 with 30,
as shown in Figure 23.14d.