Heap Sort
Heap Sort is an efficient sorting algorithm that leverages a data structure called Binary Heap to organize and sort data. It works by first building a heap from the data and then repeatedly extracting the largest (or smallest) element from the heap and rebuilding the heap until all elements are sorted. This method is known for its reliable performance and in-place sorting capabilities, making it a strong choice for handling large datasets without requiring extra memory.
Pseudocode
function heapify(i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n:
if arr[left] > arr[largest]:
largest = left
if right < n:
if arr[right] > arr[largest]:
largest = right
if largest != i:
swap(i, largest)
heapify(largest)
Visualizer
for i = (n / 2 - 1) down to 0:
heapify(i)
for i = n - 1 down to 1:
swap(0, i)
heapify(0)
Select number of elements:
How It Works
Heap Sort operates in two main phases. First, it transforms the input array into a Max Heap — a complete binary tree where every parent node is greater than or equal to its children. This is done by calling a "heapify" procedure on each non-leaf node, starting from the bottom of the tree and moving upward. Once the Max Heap is built, the largest element is guaranteed to be at the root. The algorithm then swaps the root with the last element of the heap, reduces the heap size by one, and calls heapify on the new root to restore the heap property. This process repeats until only one element remains, producing a fully sorted array.
When to Use
Heap Sort is ideal when you need guaranteed O(n log n) worst-case performance with O(1) extra space — a combination that neither Quick Sort (O(n²) worst case) nor Merge Sort (O(n) extra space) can offer. It is commonly used in systems with strict memory constraints. However, Heap Sort is not stable and tends to have worse cache performance than Quick Sort due to its non-sequential memory access patterns.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Best Case | O(n log n) | Heap Sort always builds the heap and extracts elements, regardless of input order. |
| Average Case | O(n log n) | The heap operations are consistent across all input distributions. |
| Worst Case | O(n log n) | Like Merge Sort, Heap Sort guarantees O(n log n) performance in all cases. |
| Space Complexity | O(1) | Heap Sort is an in-place algorithm — it sorts within the original array using only a constant amount of extra memory. |
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.