Heap sort

From Algorithmist

This is a stub or unfinished. Contribute by editing me.

Heap sort is an efficient sorting algorithm implemented with the heap data structure.

[edit] Algorithm

1. Build a heap with the sorting array, using recursive insertion.
2. Iterate to extract n times the maximum or minimum element in heap and heapify the heap.
3. The extracted elements form a sorted subsequence.

[edit] Pseudocode

Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], A[i])
        n = n - 1
        Heapify(A, 1)

BuildHeap(A as array)
    n = elements_in(A)
    for i = floor(n/2) to 1
        Heapify(A,i)

Heapify(A as array, i as int)
    left = 2i
    right = 2i+1

    if (left <= n) and (A[left] > A[i])
        max = left
    else 
        max = i

    if (right<=n) and (A(right] > A[max])
        max = right

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, max)

[edit] Implementations

• C in-place non-recursive