Saturday, February 07, 2009

heapsort

In heapsort,
- First put the elements of the array in a heap property (max-heap has the greater elements as parents) so that the first element is the max.
- The first element (root of heap) is swapped with the last element of the array (last leaf node of the heap) and the array is again put in heap property by sifting up or sifting down.


Sift-Down version: The sift-down version sifts the root or start down the heap. 

The sift-down version takes O(logn) time.
heapsort-siftdown(a):
    maxheapify-siftdown(a)
    end = a.length-1
    while end > 0:
        swap(a, 0, end)
        end--
        siftdown(a, 0, end)

maxheapify-siftdown(a):
    start = a.length/2 -1 // last parent
    while start >= 0:
        siftdown(a, start, a.length-1)
        start--

siftdown(a, start, end):
    left = start*2 +1
    right = left +1
    max = start
    if left <= end && a[left] > a[max]:
        max = left
    if right <= end && a[right] > a[max]:
        max = right
    if max != start:
        swap(a, start, max)
        siftdown(a, max, end)


Sift-Up version: The sift-up version builds the heap top-down as if starting with an empty heap and inserting new nodes. The child or end is sifted up to the root.

The sift-up version takes O(logn) time.
heapsort-siftup(a):
    maxheapify-siftup(a, a.length-1)
    end = a.length-1
    while end > 0:
        swap(a, 0, end)
        end--
        maxheapify-siftup(a, end)

maxheapify-siftup(a, end):
    child = 1
    while child <= end:
        siftup(a, child)
        child++

siftup(a, end):
    child = end
    while child > 0:
        parent = (child-1) /2
        if a[parent] > a[child]:
            break
        swap(a, parent, child)
        child = parent


The heap-sort with either version has O(nlogn) time efficiency.

2 comments:

  1. There is a nuance here to sifting up. It works in the context of maxHeapify, however, the call to siftUp(0, end) can't be swapped in-place for the call to siftDown(0, end) as indicated by your comments in your heapSort while loop because it won't repair the tree. A call to maxHeapify(array, end) that implements upward sifting would repair it (provided that the variable `end` is decremented after and not before).

    ReplyDelete