Advanced Sorting - Advanced Topics in Java: Core Concepts in Data Structures - page 258

1

37

2 3

84

25

4

5 6 7

79 73

69 43

12

11

9

8 10

32

18 65 56 48

Figure 9-5. A heap, except for nodes 1 and 2

Consider Figure 9-5 .
Except for nodes 1 and 2, all the other nodes satisfy the heap property in that they are bigger than or equal to their
children. Suppose we want to make node 2 the root of a heap. As it is, the value 25 is smaller than its children (79 and 69).
We want to write siftDown so that the following call will do the job:

siftDown(25, num, 2, 12)

Here, 25 is the key , num is the array, 2 is the root, and 12 is the position of the last node.
After this, each of nodes 2 to 12 will be the root of a heap, and the following call will ensure that the entire array
contains a heap:

siftDown(37, num, 1, 12)

The gist of siftDown is as follows:

find the bigger child of num[root]; //suppose it is in node m
if (key >= num[m]) we are done; put key in num[root]
//key is smaller than the bigger child
store num[m] in num[root] //promote bigger child
set root to m

The process is repeated until the value at root is bigger than its children or there are no children. Here is siftDown :

public static void siftDown(int key, int[] num, int root, int last) {
int bigger = 2 * root;
while (bigger <= last) { //while there is at least one child
if (bigger < last) //there is a right child as well; find the bigger
if (num[bigger+1] > num[bigger]) bigger++;
//'bigger' holds the index of the bigger child
if (key >= num[bigger]) break;
//key is smaller; promote num[bigger]
num[root] = num[bigger];
root = bigger;
bigger = 2 * root;
}
num[root] = key;
} //end siftDown