Sat Apr 24 2021

Heap Sort

Heap sort is a comparison-based sorting algorithm. Heap sort is based on the heap data structure. The asymptotic performance of Heap sort is O(n log n) in the best, average, and worst cases. It is not as fast as Quick sort in the average case, but Heap sort has special properties that will make it particularly useful when sorting data sets too large to fit in main memory.

The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element. it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the smallest element and moving that to the sorted region.

File Name: heap-sort-algorithm.c

# heapify
for i = n/2:1, sink(a,i,n)
	invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    	invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)
    return result

Reference:

Heap Sort

Author:Geekboots