|
The heapsort algorithm was invented by english mathematician J.Williams. It is based on
convenient numeration of binary tree's vertices and conformity of a tree to an array.
Lets take a full binary tree with branches of height k. Such tree has 2(k+1) - 1
vertices (so dependence of tree height on vertices number is approximately logariphmic). Really,
root vertex forms zero layer of the tree, and then each horizontal layer has twice more number
of vertices then previous one. So k-th layer has 2k vertices. If we renumber vertices
from top to bottom and from left to right, we'll see that vertex with number s will be connected
with vertices 2s and 2s + 1 of the next layer(these are children of vertex s).
Hierarchical sorting is based on this way of numeration. Each array's index is corresponded to
single vertex and array's (let it h[1:n]) items may be considered as binary tree's vertices.
Sorting is performed in terms of this tree. The simple arithmetic conformity of connected vertices'
numbers lets get the corresponding indexes.
The sorting consists two phases. The first phase maintains hierarchical ordering of the array:
the value of each vertex must be worse (usually "worse" is "more" because sorting is traditionally
performed by increase) then values of both children. For this purpose we use operation of sifting
the item. The current item is compared with the worst child, and if the worst child is worse then
current item, they are swapped, then comparing (and, if necessary, swapping) is performed for
the new current item(until we reach the last tree's layer). Such operation is performed for all
items starting from number [n/2] (why not from number n?) and ending the first.
The second phase consists from sequental executing next operations. Take the worst item
(now it is on first place, but must be on last), swap it with last item, decrease the quantity of
tree's vertices by detaching the last item from the tree, restore the hierarchical ordering by
sifting the new first tree item. In the end, when all array's items become detached from the tree,
the array will be fully sorted.
|