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 \(\Theta(n \log n)\)

  • Unstable - relative order of equal elements is not preserved

Algorithm Details

  1. Heapify the array to build a heap

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

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 \(\Theta(n \log n)\)

  • Space \(\Theta(1)\) as an in-place algorithm

Visualization