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

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:

  1. Build a max heap of the input array; this is often called heapify.
  2. Because the first element by definition is the largest , swap it with the last element.
  3. 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 &gt;= 0; i-- ) {
     heapify( arr, size, i );
   }
   // Swap the first element, then continue to heapify all elements.
   Int i = size - 1;
   while ( i &gt; 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 &lt; size &amp;&amp; arr[leftLeaf] &gt; arr[largest] ) {
     largest = leftLeaf;
   }
   // If the right child is larger than the current largest.
   if ( rightLeaf &lt; size &amp;&amp; arr[rightLeaf] &gt; 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