Java Reference
In-Depth Information
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
.
Search WWH ::
Custom Search