# Heap Sort

Heap sort is a comparison-based sorting technique based on the Binary Heap. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.

Make sure to understand the Heapify operation.

Here’s another way to look at heap sort, as explained by teacher Olga

The advantage is that memory complexity of $O(1)$.

```
def _lower(data, k, n):
'''This is the critical step of the heap creation
process. The idea is that, after a deletion, we have
to demote a key that now violates the heap principle.'''
j = k * 2 + 1
while j < n:
if j < n - 1:
if data[j] < data[j + 1]:
j += 1 # right child
if data[k] >= data[j]:
break
data[j], data[k] = data[k], data[j]
k = j
j = k * 2 + 1
def heapsort(data):
'''
heap sort an array using a priority queue.
This implements an in-place, N log N sort.
'''
# Create a priority queue from the initial array.
n = len(data) - 1
i = (n - 1) // 2
while i >= 0:
_lower(data, i, n + 1)
i -= 1
# Now we essentially sort the array by taking the maximum
# element, swapping it to the back of the array, and then
# 'sinking' the old last element to its proper position.
while n >= 0:
data[0], data[n] = data[n], data[0]
_lower(data, 0, n)
n -= 1
```