CS205

Heap Sort

O(n log n)

Builds a max-heap and repeatedly extracts the maximum element.

Heap Sort
64
34
25
12
22
11
90
0
1
2
3
4
5
6
Ready to start
Step 0 of 0
Speed:500ms
Default
Comparing
Swapping
Sorted
Pivot
Algorithm Info

Builds a max-heap and repeatedly extracts the maximum element.

Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(n log n)
Space
O(1)
How It Works
  1. Build a max-heap from the unsorted array
  2. The largest element is now at the root (index 0)
  3. Swap root with the last element in the heap
  4. Reduce heap size by 1 (excluding sorted elements)
  5. Heapify the root to restore max-heap property
  6. Repeat until heap size is 1
Pseudocode
heapSort(arr):
    n = arr.length

    // Build max heap
    for i = n/2 - 1 down to 0:
        heapify(arr, n, i)

    // Extract elements one by one
    for i = n-1 down to 1:
        swap(arr[0], arr[i])
        heapify(arr, i, 0)

heapify(arr, heapSize, rootIndex):
    largest = rootIndex
    left = 2 * rootIndex + 1
    right = 2 * rootIndex + 2

    if left < heapSize and arr[left] > arr[largest]:
        largest = left
    if right < heapSize and arr[right] > arr[largest]:
        largest = right
    if largest != rootIndex:
        swap(arr[rootIndex], arr[largest])
        heapify(arr, heapSize, largest)
Complexity Analysis
Time Complexity
Best:O(n log n)
Average:O(n log n)
Worst:O(n log n)
Space Complexity
O(1)
Stable Sort?
No
Advantages & Disadvantages
Advantages
  • Guaranteed O(n log n) time in all cases
  • In-place sorting - O(1) extra space
  • No worst-case scenario like quicksort
  • Good for finding k largest/smallest elements
  • Useful in priority queue implementations
Disadvantages
  • Not stable - may change order of equal elements
  • Poor cache performance (jumps around in memory)
  • Slower than quicksort in practice for random data
  • More complex than simple O(n^2) algorithms
When to Use Heap Sort
  • •When worst-case O(n log n) guarantee is needed
  • •Memory-constrained environments (in-place)
  • •Finding k largest or smallest elements
  • •Priority queue operations
  • •Embedded systems with limited memory