# Heap sort

 Sorting Algorithms Bubble sort Insertion sort Selection sort Quicksort Merge sort Heap sort Introsort Counting sort Problems Problems solvable using sorting
 This is a stub or unfinished. Contribute by editing me.

Heap sort is an efficient sorting algorithm implemented with the heap data structure. Time Complexity for all cases is O(n(log n)) and Space Complexity is O(1).

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

## 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,n)

Heapify(A as array, i as int, n 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)
```

## Implementations

• C in-place non-recursive

////////////////////////