A+DS

Heap Sort

Build a heap, extract the max repeatedly.

Imagine a tournament bracket where the winner (largest) always rises to the top. Heap Sort first arranges the array into a "max heap" where the parent is always larger than its children. Then it repeatedly extracts the maximum and places it at the end.

       [ MAX ]           max-heap
      /       \
    [  ]     [  ]         parent > children
   /  \     /  \
  [] [] [] []

  swap MAX to end → [ ? ? ? ... ✔ ]
  re-heapify and repeat!

How it works

  1. 1Build a max-heap from the array
  2. 2The largest element is at the root (index 0)
  3. 3Swap it with the last unsorted element
  4. 4Shrink the heap by one and re-heapify

Loading...