The Heap Sort
By Samuel Marateck (c) 2000
The definition of a heap is a complete binary tree in which the value
stored in the parent is greater than or equal to that stored in each
of its children. Although a tree is used to explain how a heap works,
the program uses an array to represent the heap. All operations
are done on the array.
The heap sort starts with a tree that's a heap. We will work with the
following initial example with N, the number of nodes equal to 6:
r
/ \
p m
/ \ /
o k c
The initial array configuration corresponding to this is: rpmokc.
We exchange the root with the last node on the tree, c.
c
/ \
p m
/ \ /
o k r
The r is now in its proper place in the sorted array: cpmokr. So we
set N to 5, therefore working only with cpmok, and the tree
representing the heap becomes:
c
/ \
p m
/ \
o k
The tree, however, is no longer a heap. We see which of c's children
is the larger, here it's p, and swap it with c. So the tree is now:
p
/ \
c m
/ \
o k
It's still not a heap. We continue down the subtree which has c as its
root. The reason we don't have to worry about the subtree with m as
its root is that that subtree is already a heap. We see which of c's
children is the larger, here it's o, and swap it with c. So the tree
is now:
p
/ \
o m
/ \
c k
This process is called reheapification. The tree is now a heap and the
corresponding array, including the r is pomckr. Next we exchange the
root p with k
k
/ \
o m
/ \
c p
The array is now komcpr. The p and r are now in their proper place in
the array. So we set N to 4 and the tree becomes
k
/ \
o m
/
c
Reheapification yields
o
/ \
k m
/
c
We exchange the root o with the last node on the heap and get
c
/ \
k m
/
o
The array is now ckmopr. Now the opr are in their proper place in the
array. So we set N to 3 and deal with
c
/ \
k m
Reheapification yields
m
/ \
k c
After the exchange we get
c
/ \
k m
The array becomes ckmopr and mopr are in their proper place in the
array. Set N to 2 and the tree becomes:
c
/
k
Reheapification yields
k
/
c
The exchange produces
c
/
k
and the array becomes ckmopr and the sort is finished.
The time analysis for reheapification is O(logN) since it depends on
the number of levels in the tree. Since there are N items in the list,
an upper limit for heap sort is O(NLogN).