# Heap Sort

Data Structure1285 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.

## 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: