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.