#### Apr 24, 2021

# Heap Sort

Data Structure 1015 views

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.

# 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