DSA — Sorting Algorithms

Heap Sort

Build a max-heap in O(n), then repeatedly extract the max to sort. Guaranteed O(n log n) with O(1) space.

— min read
O(n log n)All Cases
O(1)Space
UnstableSort
In-placeAlgorithm
HeapBuild O(n)
// HEAP SORT — LIVE ANIMATION
Speed
Press ▶ Sort to begin
How It Works
Python Code
Complexity
Quiz
Practice
01
Build Max-Heap
Heapify bottom-up — O(n) total.
for i in range(n//2-1,-1,-1): heapify(arr,n,i)
02
Extract Max
Swap root (max) with last element, shrink heap.
arr[0], arr[i] = arr[i], arr[0]
03
Heapify Down
Restore heap property from root — O(log n).
heapify(arr, i, 0)
04
Repeat
Extract n-1 times. Total O(n log n).
python 
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[0], arr[i] = arr[i], arr[0]
        heapify(arr,i,0)

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)
O(n log n)
Always
Guaranteed — no bad pivot problem
O(1)
Space
In-place — beats Merge Sort on space
O(n)
Build Heap
Bottom-up heapification is linear
Unstable
Equal elements
Long-range swaps break stability
Time complexity to build a max-heap from n elements?
Progress 0 / 5 solved
5 problems · 3 PBC · 2 Startup
#1851 Kth Largest Element in Array Amazon, Google PBC →
#1852 Top K Frequent Elements Meta, Amazon PBC →
#1853 Find Median from Data Stream Google, Meta PBC →
#1854 K Closest Points to Origin Meesho STARTUP →
#1855 Last Stone Weight Swiggy STARTUP →
← Quick Sort