selection steps requires only log(ncomparisons thereforethe total selection process requires only on the order of *log(nelementary operations in addition to the steps required by the construction of the tree this is very significant improvement over the straight methods requiring stepsand even over shellsort that requires steps naturallythe task of bookkeeping has become more elaborateand therefore the complexity of individual steps is greater in the tree sort methodafter allin order to retain the increased amount of information gained from the initial passsome sort of tree structure has to be created our next task is to find methods of organizing this information efficiently fig selecting the least key fig refilling the holes of courseit would seem particularly desirable to eliminate the need for the holes that in the end populate the entire tree and are the source of many unnecessary comparisons moreovera way should be found to represent the tree of items in units of storageinstead of in units as shown above these goals are indeed achieved by method called heapsort by its inventor williams [ - ]it is plain that this method represents drastic improvement over more conventional tree sorting approaches heap is defined as sequence of keys hlhl+ hr ( > such that hi + and hi + for / - if binary tree is represented as an array as shown in fig then it follows that the sort trees in figs and are heapsand in particular that the element of heap is its least elementh min( hn- fig array viewed as binary tree