Heapsort: Creating a Heap

• An arbitrary list can be turned into a heap by calling FixHeap on each non-leaf in reverse order.

• If n is the size of the heap, the non-leaf with the highest index has index n/2.

• Creating a heap is obviously O(n lg n).

• A more careful analysis would show a true time bound of ?(n)

Previous slide

Next slide

Back to first slide

View graphic version