Heapsort. Automatic generation of vizualizer's logic


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.


Autor: G.G. Udov. Vizualization technology: G.A. Korneev. Supervizor: A.A. Shalyto

St'Petersburg state university of information technologies, mechanics and optics.
Department "Computer technologies"

Copyright 2003 by Georgy G. Udov