Optimizing heap structure for heapsort

Question

I'm implementing heapsort using a heap. To do this each value to be sorted is inserted. The insertion method calls heapifyUp() (aka siftUp) so this means each time another value is inserted heapifyUp is called. Is this the most efficient way?

Another idea would be to insert all elements, and then call heapifyUp. I guess heapifyUp would have to be called on each one? Is doing it like this better?

Answer 1

Inserting each element will build the heap in O(n log n) time. Same thing if you add all the elements to an array and then repeatedly call heapifyUp().

Floyd's Algorithm builds the heap bottom-up in O(n) time. The idea is that you take an array that's in any order and, starting in the middle, sift each item down to its proper place. The algorithm is:

for i = array.length/2 downto 0
{
    siftDown(i)
}

You start in the middle because the last length/2 items in the array are leaves. They can't be sifted down. By working your way from the middle, up, you reduce the number of items that have to be moved.

Example of the difference

The example below, turning an array of 7 items into a heap, shows the difference in the amount of work done.

The heapifyUp() method

[7,5,6,1,2,3,4]  (starting state)

Start at the end and bubble items up.

Move 4 to the proper place

[7,5,4,1,2,3,6]
[4,5,7,1,2,3,6]

Move 3 to its place

[4,5,3,1,2,7,6]
[3,5,4,1,2,7,6]

Move 2 to its place

[3,2,4,1,5,7,6]
[2,3,4,1,5,7,6]

Move 1 to its place

[2,1,4,3,5,7,6]
[1,2,4,3,5,7,6]

The heap is now in order. It took 8 swaps, and you still have to check 4, 2, and 1.

Floyd's algorithm

[7,5,6,1,2,3,4]  (starting state)

Start at the halfway point and sift down. In a 0-based array of 7 items, the halfway point is 3.

Move 1 to its place

[7,5,6,1,2,3,4]  (no change. Remember, we're sifting down)

Move 6 to its place

[7,5,3,1,2,6,4]

Move 5 to its place

[7,1,3,5,2,6,4]
[7,1,3,4,2,6,5]

Move 7 to its place

[1,7,3,5,2,6,4]
[1,2,3,5,7,6,4]

And we're done. It took 5 swaps and there's nothing else to check.