Codacoda
Back to Academy

sorting

Heap Sort

Heap Sort builds a max-heap from the input array and then repeatedly extracts the maximum element from the heap, placing it at the end of the sorted portion of the array. It combines the efficiency of merge sort with the in-place advantage of insertion sort, guaranteeing O(n log n) performance without requiring extra memory.

Use Cases

  • •When guaranteed O(n log n) worst-case is needed without extra memory
  • •Priority queue implementations
  • •Systems where consistent performance is more important than raw speed

Complexity Analysis

MetricBestAverageWorst
TimeO(n log n)O(n log n)O(n log n)
SpaceO(1)

Visualization

64
34
25
12
22
11
90
Speed:1x
Initial arrayStep 1 / 39

Implementation

Output

Click "Run Code" to see output...