Heap Sort Algorithm: Heapify, Build Heap, O(n log n), and In-Place Sort (2026)
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element (the root) and places it at the end of the array. The heap is rebuilt after each extraction until the entire array is sorted.
This tutorial covers the heapify operation, building a heap, the sorting phase, complexity analysis, and the in-place property of Heap Sort. Code examples are provided in C++, Java, and Python.
Heapify and Build Heap Operations
Heapify ensures that a subtree rooted at index i satisfies the max-heap property: the parent is greater than or equal to both children. It recursively (or iteratively) percolates the element down until the property holds. Building a heap from an unsorted array is done by calling heapify on all non-leaf nodes from n/2 - 1 down to 0.
Building a heap takes O(n) time — a tighter bound than the intuitive O(n log n) because most nodes are near leaves and require fewer comparisons. The heapify operation itself takes O(log n) in the worst case (height of the tree).
// C++
void heapify(int arr[], int n, int i) {
int largest = i, l = 2*i+1, r = 2*i+2;
if(l < n && arr[l] > arr[largest]) largest = l;
if(r < n && arr[r] > arr[largest]) largest = r;
if(largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void buildHeap(int arr[], int n) {
for(int i = n/2-1; i >= 0; i--)
heapify(arr, n, i);
}
// Java — similar heapify logic
// Python
def heapify(arr, n, i):
largest = i
l, r = 2*i+1, 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)
def build_heap(arr):
for i in range(len(arr)//2-1, -1, -1):
heapify(arr, len(arr), i)Sorting Phase and Complexity
After building the max-heap, the sorting phase repeatedly swaps the root (maximum element) with the last element of the heap, reduces the heap size by one, and calls heapify on the root to restore the max-heap property. This is done until the heap size becomes 1.
Heap Sort has O(n log n) time complexity in all cases (best, average, worst). Space complexity is O(1) — it sorts in place with only a few variables for indices. Heap Sort is not stable because the heap operations can reorder equal elements. Unlike Quick Sort, Heap Sort has no O(n²) worst case, making it suitable for safety-critical systems.
// C++
void heapSort(int arr[], int n) {
buildHeap(arr, n);
for(int i=n-1; i>0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
// Java
void heapSort(int[] arr) {
buildHeap(arr);
for(int i=arr.length-1; i>0; i--) {
int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
heapify(arr, i, 0);
}
}
// Python
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap
return [heapq.heappop(arr) for _ in range(len(arr))]Frequently Asked Questions
What is the time complexity of Heap Sort?
O(n log n) for all cases. Building the heap takes O(n), and each of the n heapify operations takes O(log n).
Is Heap Sort stable?
No, Heap Sort is not stable. The heap extraction and heapify operations can change the relative order of equal elements.
Originally published on Ayodhyyya. Last updated June 1, 2026.