HeapSort

@heapsort

HeapSort is a sorting algorithm that uses a special tree structure called a heap. It repeatedly takes the largest element and moves it to the end, shrinking the unsorted part step by step until everything is sorted.

Pseudo-code
function heapsort(heap):
  n = length(heap)

  # Step 1: Build a max heap (largest element at top)
  build_heap(heap, n)

  # Step 2: Repeatedly extract the largest element
  for i from n down to 2:
    swap(heap[1], heap[i])   # move largest to the end
    n = n - 1                # reduce heap size
    heapify(heap, n, 1)     # fix the heap from the root

  return heap

function build_heap(heap, n):
  # Start from last non-leaf node and go upward
  for i from n//2 down to 1:
    heapify(heap, n, i)

function heapify(heap, n, i):
  largest = i
  left = 2 * i
  right = 2 * i + 1

  # Check if left child is bigger
  if left <= n and heap[left] > heap[largest]:
    largest = left

  # Check if right child is bigger
  if right <= n and heap[right] > heap[largest]:
    largest = right

  # If the largest is not the parent, swap and continue
  if largest != i:
    swap(heap[i], heap[largest])
    heapify(heap, n, largest)
  • heap Main list we are sorting, but we treat it like a tree (heap structure).
  • left Left child of a node. In an array, its position is calculated (like 2*i).
  • right Right child of a node (like 2*i + 1).
  • largest Tracks the biggest value among a node and its children so we can keep the heap correct.
  • n Current size of the heap (unsorted portion).
Recipe Steps
1

Turn your list into a pyramid — Imagine stacking numbers like a pyramid where the biggest number is always on top.

2

Take the top (biggest) — Remove the top element and place it at the end of your list (this is its final sorted position).

3

Fix the pyramid — After removing the top, the structure is broken, so you rebuild it to make sure the biggest is on top again.

4

Repeat: take the biggest again, move it to the end, and fix the heap.

5

Keep going until nothing is left in the heap. Now your list is fully sorted.

Questions & Answers

Always keep track of the largest element using a heap, and move it to its correct final position.

To fix the heap structure so the largest element is always at the top.

A max heap, where parents are always bigger than children.

At the root (top) of the heap.
- Time complexity is always O(n log n), no worst-case surprises.
- HeapSort does not need extra memory like MergeSort.
- Tip: Think of the heap as a binary tree stored in an array.
- Common mistake: Forgetting to reduce heap size after each extraction.
- Indexing often starts at 1 in explanations, but real code usually uses 0-based indexing.

Related Algorithms
Backtracking

Backtracking is a problem-solving technique used in algorithms to find a solution by exploring all possible solutions and retracting when a dead end is reached. It's often used for solving puzzles, finding paths, or scheduling tasks.

View
Binary Search

Binary Search is a very fast algorithm used to find a value in a sorted list by repeatedly cutting the search space in half until the item is found or nothing is left.

View
Boyer–Moore string-search algorithm

The Boyer–Moore string-search algorithm is a fast string searching algorithm that is often used in text editors and compilers. It does this by trying to match the pattern from the end of the string, making it efficient for large strings. It's used when you need to find a substring within a large text or string.

View