The Least Basic Operations on Heap and Improved Heapsort

The best algorithms of INSERT and DELETE operations on heap is presented,by which HEAPSORT is improved. Inserting one element into and deleting one element from a heap of n elements spend at most loglogn comparisons and logncomparisons and transfers of element in the worst cases respectively. The improved HEAPSoRT spends n log n + n log logn + O(n) comparisons and element transfers (notswapl) in the worst case. It may be the best HEAPSORT algorithm since the lower bound of sorting algorithm log nl n l…