|
Once a heap has been built, a Heapsort can simply remove the maximum
value (root node) and create the output, sorted array one item at a
time. This process is somewhat akin to the Selection Sort but much
more efficient.
When the root node in a heap is removed to become part of the final,
ordered data set, the last item on the heap is promoted to fill the
vacancy at the root position. Clearly, in many cases, this last item
will now be out of place (that is, it may be smaller than one of its
new children). To ensure that the modified heap retains the max-heap
property it becomes necessary to ``push down'' the newly promoted
root item until it is back in the right place. This pushing down
process entails examining the node's key value and comparing it with
the key value of the node's greatest child. If the node's greater
child is larger in value than the node itself, a swap is performed.
The process repeats, following the node from the root down through
demotion, until no swap is needed. At this point the heap is back in
order, the new root may be popped off, and the sorting process can
continue.
The process of removing the root, promoting the last node, and
re-heapifying continues until the heap is exhausted.
|
Search