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

At this stage, the second largest number, 79, is in node 1. This is placed in node 11, and 48 is “sifted down” from
node 1 until items 1 to 10 form a heap. Now, the third largest number, 73, will be at the root. This is placed in node 10,
and so on. The process is repeated until the array is sorted.
After the initial heap is built, the sorting process can be described with the following pseudocode:

for k = n downto 2 do
item = num[k] //extract current last item
num[k] = num[1] //move top of heap to current last node
siftDown(item, num, 1, k-1) //restore heap properties from 1 to k-1
end for

where siftDown(item, num, 1, k-1) assumes that the following hold:
•

num[1] is empty.

num[2] to num[k-1] form a heap.
Starting at position 1, item is inserted so that num[1] to num[k-1] form a heap.
In the sorting process described above, each time through the loop, the value in the current last position ( k ) is
stored in item . The value at node 1 is moved to position k ; node 1 becomes empty (available), and nodes 2 to k-1 all
satisfy the heap property.
The call siftDown(item, num, 1, k-1) will add item so that num[1] to num[k-1] contain a heap. This ensures
that the next highest number is at node 1.
The nice thing about siftDown (when we write it) is that it can be used to create the initial heap from the given
array. Recall the process of creating a heap described in Section 9.1.1. At each node ( h , say), we “sifted the value
down” so that we formed a heap rooted at h . To use siftDown in this situation, we generalize it as follows:

•

void siftDown(int key, int num[], int root, int last)

This assumes the following:

num[root] is empty. •

last is the last entry in the array, num . •

num[root*2] , if it exists ( root*2 £ last ), is the root of a heap.

•

num[root*2+1] , if it exists ( root*2+1 £ last ), is the root of a heap.
Starting at root , key is inserted so that num[root] becomes the root of a heap.
Given an array of values num[1] to num[n] , we could build the heap with this pseudocode:

•

for h = n/2 downto 1 do // n/2 is the last non-leaf node
siftDown(num[h], num, h, n)

We now show how to write siftDown .