There are instances in computer science and mathematics where you can solve a problem using knowledge about a different, but similar subject. A nice example of this is Heap Sort, which exploits properties of heaps to help sort arrays quickly.

### Assumptions

- Knowledge of <a href="https://www.devmaking.com/learn/algorithms/big-o-notation/" target="_blank" style="color:inherit">Big-O notation</a>
- Prior knowledge of heaps will help, but is not required.

# What is Heap Sort?

Heap Sort is a *comparison-based* sorting algorithm that exploits properties of **binary heaps** to sort an array.
Heap Sort is often referred to as an improved selection sort as it iteratively shrinks the amount of unsorted elements.

> Heap Sort is not stable, but it is in-place.

## Heaps and Binary Trees

A **Binary Tree** is a data structure that is composed of "nodes" with left and right sub-trees. There are different rules that can govern how the tree is set up.
One configuration of a binary tree is called a *Complete Binary Tree*; A binary tree that has all of its level's filled, with an exception for the bottom level which does not need to be completely full.

> While this definition says that the tree is represented by nodes, it is also possible to format a Complete Binary Tree as an array.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/HeapSort_01.png" alt="complete-binary tree" style="width:500px;max-width:95%;">

</div>

A **Heap** is a type of Complete Binary tree that arranges the nodes in a certain order that helps the tree stay in complete order. Heaps usually come in two types; *min-Heaps* and *max-Heaps*.
For Heap Sort, we will be taking advantage of the properties of a max-heap to help sort an array.

### Max Heap

A **max-heap** sorts elements in order of largest to smallest, where a parent node must be larger than it's two children nodes.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/HeapSort_02.png" alt="max-heap diagram" style="width:500px;max-width:95%;">

</div>

> A min-heap is the opposite of this, where the parent node is smaller than the two children nodes.

## Heap Sort

Heap sort works by following these steps:

- Build a max heap of the input array; this is often called
`heapify`

. - Because the first element by definition is the largest , swap it with the last element.
- Repeat steps 1 and 2, decreasing the size of the heap by 1 each iteration until the array is sorted.

```
/* pseudo-code */
function heapSort( int[] arr ) {
int size = arr.length;
// Heapify the array.
for ( int i = size / 2 - 1; i >= 0; i-- ) {
heapify( arr, size, i );
}
// Swap the first element, then continue to heapify all elements.
Int i = size - 1;
while ( i > 1 ) {
// Swap the first with arr[i].
swap( arr, 0, i);
// Heapify the array again.
heapify( arr, i, 0 );
// Then decrement i.
i--;
}
}
// Auxiliary swap function.
function swap( int[] arr, int a, int b ) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
// Implementation of heapify.
// Builds a max-heap out of the remaining elements.
function heapify( int[] arr, int size, int i ) {
int largest = i;
// i-th element's left child.
int leftLeaf = 2*i + 1;
// i-th element's right child.
int rightLeaf = 2*i + 2;
// If the left child is larger than the current largest.
if ( leftLeaf < size && arr[leftLeaf] > arr[largest] ) {
largest = leftLeaf;
}
// If the right child is larger than the current largest.
if ( rightLeaf < size && arr[rightLeaf] > arr[largest] ) {
largest = rightLeaf;
}
// If the largest of the two is not the original largest
if ( largest != i ) {
// Swap i and the largest.
swap ( arr, i, largest );
// Heapify the sub-tree.
heapify ( arr, size, largest );
}
}
```

## Analysis of Heap Sort

Worst/Average | Memory |
---|---|

O(n log n) | O(1) |

Taking this step by step:

- Heapify the the array.
- Place the first (largest) element at the end of the array.
- Repeat with the
`n - 1`

array.

Once the original array is heapified, the following heapify function calls should only need to perform at most **O(log n)** operations to re-heapify the array. This is corresponding to the depth of the Binary Heap.

In addition to this, we heapify the array for every element, which introduces a **O(n)** complexity in addition to the original **O(log n)**.

The final complexity of Heap Sort works out to be **O(n log n)**.

## When to use Heap Sort

Heap Sort itself is not used frequently in practice, however it does have a very useful application of being able to find the minimum and maximum elements in an array while the array is being processed.
Additionally, it's worst case performance of **O(n log n)** makes it a comparable algorithm to other's such as Quicksort and Merge sort.

## Further Resources

- <a href="https://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X/ref=as_li_ss_tl?_encoding=UTF8&pd_rd_i=032157351X&pd_rd_r=37c135e7-c5c4-4ed1-94ab-c2aaec60d692&pd_rd_w=PEuac&pd_rd_wg=xSJkC&pf_rd_p=1c11b7ff-9ffb-4ba6-8036-be1b0afa79bb&pf_rd_r=H3XK6W265MFMNYZ7PV3Z&psc=1&refRID=H3XK6W265MFMNYZ7PV3Z&linkCode=ll1&tag=devmaking-20&linkId=9f9600161b287607f80038c5fd85b020&language=en_US" target="_blank" style="color:#fff;border-radius:3px;background-color:#888;padding:1px 5px">Algorithms (Sedgwick)</a> An excellent resource and reference for learning algorithms in computer science.
- <a href="https://www.amazon.com/Algorithms-Sanjoy-Dasgupta-ebook-dp-B006Z0QR3I/dp/B006Z0QR3I/ref=as_li_ss_tl?_encoding=UTF8&me=&qid=1566246918&linkCode=ll1&tag=devmaking-20&linkId=26b190aacb9c02d1a0815d4066f9d80e&language=en_US" target="_blank" style="color:#fff;border-radius:3px;background-color:#888;padding:1px 5px">Algorithms (Dasgupta)</a> Concise and clear overview on various types and designs of algorithms in a digestible format.
- <a href="https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844/ref=as_li_ss_tl?ie=UTF8&linkCode=ll1&tag=devmaking-20&linkId=1dd5be6066b180c12926dc03e2659215&language=en_US" target="_blank" style="color:#fff;border-radius:3px;background-color:#888;padding:1px 5px">Introduction to Algorithms (CLRS)</a> An in depth and comprehensively detailed explanation of algorithms and how to design them.