Heap Sort
A comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort.
Visualization
Details
Analogy
Consider a company's hierarchical org chart structured as a 'max heap' where every manager earns more than their direct reports. The CEO at the top is the highest-paid. You 'remove' the CEO, promote the next highest earner, and re-organize the chart to find the next highest, repeating until everyone is sorted by salary.
Purpose
To sort an array by first building a max heap from the data, then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted portion.
Use Cases
Useful when a guaranteed worst-case O(n log n) performance is needed. It's not stable and is generally slower in practice than a well-implemented Quick Sort.
Algorithm Steps
build max heap from array
for i = n-1 to 1:
swap arr[0] with arr[i]
heapify(arr, 0, i)
function heapify(arr, i, size):
largest = i
left = 2*i + 1
right = 2*i + 2
if left < size and arr[left] > arr[largest]:
largest = left
if right < size and arr[right] > arr[largest]:
largest = right
if largest != i:
swap arr[i] with arr[largest]
heapify(arr, largest, size)
Explanation
What's Happening?
Initial array. Start building a max heap.
Code Implementation
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)