DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Heap Sort as a Priority Queue
A clever structure that keeps "give me the biggest (or smallest) item" instantly fast.
A heap is a tree where every parent is ≥ (max-heap) or ≤ (min-heap) both its children — this property alone guarantees the maximum (or minimum) is always sitting right at the root.
Heapify example — building a max-heap from [4,10,3,5,1]:
Start with array as an implicit tree (index i's children at 2i+1, 2i+2)
Sift down from the last non-leaf node upward, swapping a parent
with its larger child whenever the max-heap property is violated.
Result after heapify: [10,5,3,4,1] (10 is now correctly at the root)
Heap sort repeatedly extracts the root (the current max), swaps it to the end of the array, shrinks the heap by one, and re-heapifies — producing a fully sorted array, always in O(n log n).
A priority queue is the natural real-world use of a heap: always serving the highest (or lowest) priority item first, in O(log n) per insert/extract — used in OS task scheduling and Dijkstra's algorithm (met later in this chapter).
💡 Practice building a max-heap from a given array (the heapify process) AND performing 2-3 extraction steps of heap sort — both halves of this topic get tested.
The extraction steps, traced
The chapter's heapify of [4,10,3,5,1] gives [10,5,3,4,1]. Here is what heap sort then does with it.
Heap: [10, 5, 3, 4, 1] (heap size 5)
EXTRACT 1 — swap root with the last heap element, shrink, re-heapify
swap 10 and 1 → [1, 5, 3, 4 | 10] heap size 4
sift 1 down → [5, 4, 3, 1 | 10]
EXTRACT 2
swap 5 and 1 → [1, 4, 3 | 5, 10] heap size 3
sift 1 down → [4, 1, 3 | 5, 10]
EXTRACT 3
swap 4 and 3 → [3, 1 | 4, 5, 10] heap size 2
sift 3 down → [3, 1 | 4, 5, 10] (already correct)
The bar marks the boundary: heap on the left, sorted tail on the right,
growing from the end backwards.
Notice that the sorted portion builds from the right. Each extraction puts the current maximum immediately before the previously extracted one, so the array finishes in ascending order without ever needing extra memory — heap sort is in-place, which is its main advantage over merge sort.
Why the array-as-tree trick works
A heap is a complete binary tree — every level full except possibly the last, which fills left to right. That is exactly the condition under which a tree can be stored in an array with no gaps and no pointers:
node at index i:
left child = 2i + 1
right child = 2i + 2
parent = (i − 1) / 2, integer division
Check on [10,5,3,4,1]: index 0 is 10, children at 1 and 2 are 5 and 3 ✓
index 1 is 5, children at 3 and 4 are 4 and 1 ✓
💡 If the tree were not complete, an array would need gaps for the missing nodes and the index arithmetic would break. Completeness is not a decoration on the definition — it is what makes the pointer-free representation possible.
Building the heap costs less than it looks
Sifting down one node costs O(log n), and there are n nodes, so heapify looks like O(n log n). It is actually O(n).
The reason: most nodes are near the bottom and barely move. Half the nodes are leaves and sift down zero levels, a quarter sift at most one level, an eighth at most two. Summing that series gives O(n), not O(n log n) — so building the heap is cheaper than the n extractions that follow, and heap sort's O(n log n) comes from the extraction phase.
💡 Start heapify from the last non-leaf node, at index n/2 − 1, and work backwards to the root. Leaves are already valid one-element heaps, so sifting them is wasted effort — and going backwards guarantees both subtrees are valid before their parent is fixed.
Syllabus points
Heap (min/max); heapify
Heap sort; priority queue
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.