Source: Comprehensive Guide to Tries, Heaps, and Priority Queues – UCF Computer Science I
Difficulty: Intermediate | Prerequisites: Arrays, basic binary tree concepts, recursion.
Tags: heap, min-heap, max-heap, binary heap, heapify, heap insert, extract min, extract max, heap delete, decrease key, increase key, build heap, complete binary tree, array-based tree, heapsort
Heaps appear in the course after you have covered basic trees and sorting. They solve a specific problem: how do you efficiently keep track of the smallest (or largest) element in a changing collection? A heap is a complete binary tree stored in a plain array, which makes it compact and cache-friendly. It is the backbone of priority queues and heapsort, and it turns up in graph algorithms like Dijkstra's shortest path. If you understand how a binary tree maps onto an array by index arithmetic, the rest follows naturally.
A heap is a complete binary tree, stored as an array, where every parent is smaller than its children (min-heap) or larger (max-heap). You can insert, delete, and extract the extreme element in O(log n) time, and you can build a heap from scratch in O(n).
Heap
A complete binary tree that satisfies the heap property: in a min-heap every parent is less than or equal to its children, and in a max-heap every parent is greater than or equal to its children. Think of it as a tree that always keeps the smallest (or largest) value sitting at the top, ready to grab.
Heap property
The ordering rule that defines the heap. Min-heap: parent ≤ children. Max-heap: parent ≥ children. This is weaker than a BST's ordering (which also orders left vs right children); a heap only cares about the parent-child relationship.
Complete binary tree
A binary tree where every level is fully filled except possibly the last, which is filled from left to right with no gaps. In simple terms, you fill the tree row by row, left to right, like reading a book.
Heapify (sift down)
The operation that restores the heap property at a single node by comparing it with its children and swapping with the smaller child (min-heap) or larger child (max-heap), then repeating downward. This is the core maintenance routine.
Bubble up (sift up)
The upward counterpart of heapify: after inserting a new element at the bottom of the heap, you repeatedly swap it with its parent until the heap property holds.
Extract min / extract max
Removes and returns the root element (the minimum in a min-heap, the maximum in a max-heap), then restores order by moving the last element to the root and heapifying down.
A heap is stored in a zero-indexed array. No explicit pointers are needed.
For a node at index i:
Parent index: (i - 1) // 2
Left child index: 2 * i + 1
Right child index: 2 * i + 2
Example: the array [1, 4, 2, 3, 9, 7, 8, 10, 14, 16] represents a valid min-heap. Index 0 holds the minimum (1), its children are at indices 1 (4) and 2 (2), and so on.
Takes an index and assumes the left and right subtrees are already valid heaps.
Compares the node with its two children.
Swaps with the smallest child (min-heap) or largest child (max-heap) if the heap property is violated.
Recurses on the swapped child's position.
Runs in O(log n) because the tree height is log n.
Append the new element to the end of the array (maintaining completeness).
Bubble up: compare with parent, swap if the new element is smaller (min-heap) or larger (max-heap) than the parent.
Repeat until the element settles or reaches the root.
Time: O(log n).
Copy the root value (the answer).
Move the last array element into position 0.
Reduce the heap size by one.
Heapify from the root downward.
Time: O(log n).
Change the key at a given index to a smaller (or larger) value.
Bubble up from that index to restore order.
Time: O(log n).
Decrease the target node's key to negative infinity (or the smallest possible value).
This causes it to bubble up to the root.
Then extract the minimum, which removes it.
Time: O(log n).
Start from the last non-leaf node (index n // 2 - 1) and heapify each node, working backwards to the root.
This bottom-up approach is more efficient than inserting elements one by one.
Time: O(n), not O(n log n). The proof relies on the fact that most nodes are near the bottom and require very little sifting.
Operation | Time | Notes |
|---|---|---|
Get min / max | O(1) | Just read index 0 |
Insert | O(log n) | Bubble up at most log n levels |
Extract min/max | O(log n) | Replace root, then heapify down |
Decrease/increase key | O(log n) | Bubble up from the changed index |
Delete | O(log n) | Decrease key + extract |
Build heap | O(n) | Bottom-up heapify, not n separate inserts |
Index formulas (zero-based):
Parent of i: (i - 1) // 2
Left child of i: 2 * i + 1
Right child of i: 2 * i + 2
Operating system schedulers use heaps to pick the next process to run: the process with the highest priority sits at the root and can be grabbed in constant time.
Heapsort is an in-place, O(n log n) comparison sort. It is not as fast as quicksort on average (due to cache behaviour), but it guarantees worst-case O(n log n), which matters in real-time systems where you cannot afford a bad run.
Students often confuse heaps with BSTs. A BST orders left vs right children (left < parent < right). A heap only orders parent vs children (parent ≤ both children in a min-heap), and the left child can be larger than the right or vice versa.
"Build heap is O(n log n)" is a common wrong answer. The bottom-up build is O(n). The O(n log n) figure would apply if you inserted elements one at a time, but the bottom-up approach is faster because most nodes are near the leaves and barely move.
Students sometimes think you can binary-search a heap because it is "sorted." A heap is not sorted; only the root is guaranteed to be the extreme value. Searching for an arbitrary element is O(n).
Forgetting that the heap must be a complete binary tree. If you leave gaps, the array indexing formulas break and the structure is no longer a valid heap.
⚠️ Know the three index formulas (parent, left child, right child) from memory. These appear in code-tracing questions.
⚠️ Be able to walk through an extract-min step by step: remove root, move last element up, heapify down, showing each swap.
⚠️ The O(n) build-heap complexity is a favourite exam point. Be ready to explain why it is O(n) and not O(n log n).
⚠️ Expect a question asking you to distinguish a heap from a BST, or to explain why you cannot do an efficient search for an arbitrary key in a heap.
True or false: In a min-heap, the left child of any node is always smaller than the right child.
Fill in the blank: The parent of the node at index 7 in a zero-indexed heap array is at index ______.
True or false: Building a heap from an unsorted array of n elements runs in O(n log n) time.
Fill in the blank: To delete an arbitrary node from a min-heap, you first set its key to ______, then call ______.
True or false: The root of a max-heap is always the largest element in the heap.
Answers: 1. False (no ordering between siblings). 2. 3 ((7-1)//2 = 3). 3. False (O(n) with bottom-up heapify). 4. negative infinity (or the smallest possible value); extract-min. 5. True.
Q: Given the min-heap array [2, 5, 3, 8, 7, 6, 4], show the array after extracting the minimum.
A: Remove 2 (the root). Move the last element (4) to index 0, giving [4, 5, 3, 8, 7, 6]. Heapify from index 0: compare 4 with children 5 and 3. Swap 4 and 3 → [3, 5, 4, 8, 7, 6]. Now 4 at index 2 has children 6 (index 5) only (index 6 is beyond the array). 4 < 6, so heapify stops. Result: [3, 5, 4, 8, 7, 6].
Q: Why is getting the minimum from a min-heap O(1) while extracting the minimum is O(log n)?
A: Getting the minimum just reads index 0, which is a single array access. Extracting it removes that element, moves the last element to the root, and then heapifies downward through up to log n levels to restore the heap property. The removal and repair cost the extra time.
Q: You have an unsorted array of 10 elements and you need the 3 smallest. Compare building a min-heap and extracting 3 times vs sorting the whole array.
A: Building the heap takes O(n) = O(10). Three extractions each take O(log n) = O(log 10). Total: roughly O(n + 3 log n). Sorting the entire array with a comparison sort takes O(n log n). For small k relative to n, the heap approach is more efficient because you avoid sorting elements you never need.
Q: Explain the difference between heapify (sift down) and bubble up (sift up).
A: Heapify starts at a node and pushes it downward by swapping with the appropriate child until the subtree satisfies the heap property. Bubble up starts at a node and pushes it upward by swapping with its parent until the path to the root satisfies the heap property. Insert uses bubble up; extract-min and build-heap use heapify.
Heaps connect directly to priority queues (covered in the next set of notes), which are the abstract interface that heaps implement. Understanding the heap operations is understanding the engine inside every priority queue.
Heaps also connect to sorting: heapsort builds a max-heap and then repeatedly extracts the maximum to produce a sorted array. Comparing heapsort with quicksort and mergesort (stability, worst-case, space) is a common exam theme.
heap, binary heap, min-heap, max-heap, heapify, sift down, sift up, bubble up, extract min, extract max, heap insert, heap delete, decrease key, increase key, build heap, complete binary tree, array-based heap, heap property, heapsort, heap vs BST, heap index formula, parent child index heap, CS 101 UCF heaps, priority queue implementation