*********
Heap Sort
*********

Overview
========
Heap sort is a comparison based sorting technique based on Binary Heap data
structure. It is similar to selection sort where we first find the maximum
element and place the maximum element at the end. We repeat the same process
for remaining element.

It is first developed by J.W.J. Williams in 1964.

Characteristics
===============
+ Comparison based (general purpose)
+ Iterative
+ In-place
+ Efficient :math:`\Theta(n \log n)`
+ Unstable - relative order of equal elements is not preserved

Algorithm Details
=================
#. Heapify the array to build a heap
#. Removing the root node repeatedly from a heap

   * move root to the sorted region by swapping it with the last leaf
   * percolate the root down

Pseudo Code
===========

.. code-block::

  function heapSort(arr):
    n = length(arr)

    # Heapify the array
    for i from n/2-1 down to 0:
      percolateDown(arr, n, i)

    # Extract elements from the heap one by one
    for i from n - 1 down to 1:
      # Swap the root (maximum element) with the last element
      swap(arr[0], arr[i])
      percolateDown(arr, i, 0)


  function percolateDown(arr, n, i):
    largest := i
    left := 2 * i + 1
    right := 2 * i + 2

    # Compare with left child
    if left < n and arr[left] > arr[largest]:
      largest := left

    # Compare with right child
    if right < n and arr[right] > arr[largest]:
      largest := right

    # If the largest element is not the root, swap them
    if largest != i:
      swap(arr[i], arr[largest])

      # Recursively percolate down the affected sub-tree
      percolateDown(arr, n, largest)

Complexity
==========
+ Time :math:`\Theta(n \log n)`
+ Space :math:`\Theta(1)` as an in-place algorithm

Visualization
=============
+ https://www.cs.usfca.edu/~galles/visualization/HeapSort.html