Difficulty: Intermediate | Prerequisites: Arrays, binary trees, Big-O notation.
Heaps sit at the crossroads of trees and arrays, and they power one of the most useful abstract data types in computer science: the priority queue. If you are comfortable with complete binary trees and array indexing, this material will click quickly. If those are fuzzy, revisit your binary tree notes first. Heaps come up constantly in interview problems and are the backbone of heapsort, Dijkstra's algorithm, and many scheduling systems.
A heap is a complete binary tree stored in an array where every parent is smaller (min-heap) or larger (max-heap) than its children. Heaps let you insert elements and pull out the smallest or largest in O(log n) time, which makes them the go-to implementation for priority queues. The clever trick is that you can build one from scratch in O(n), not O(n log n), using bottom-up heapifyDown.
Binary heap
A complete binary tree that satisfies the heap property: every node's key is ordered relative to its children. In simple terms, it is a tree that fills level by level from left to right, where each parent "wins" the comparison with both its children.
Min-heap
A binary heap where the parent node's key is less than or equal to the keys of its children. The root always holds the smallest element. Think of it as: the winner is the smallest value, and it floats to the top.
Max-heap
A binary heap where the parent node's key is greater than or equal to the keys of its children. The root always holds the largest element. The mirror image of a min-heap.
Complete binary tree
A binary tree in which every level is fully filled except possibly the last, which is filled from left to right. This is what lets us store the tree in a flat array with no wasted space.
heapifyUp (sift up / bubble up)
The operation used during insertion. Compare the newly inserted element with its parent and swap if the heap property is violated; repeat upward until the property holds. In simple terms, the new element climbs the tree until it finds its place.
heapifyDown (sift down / percolate down)
The operation used during removal of the root (min or max). Replace the root with the last element, then compare with children and swap with the appropriate child (smaller child in a min-heap, larger in a max-heap); repeat downward. Think of it as: the replacement sinks until it settles.
Priority queue (ADT)
An abstract data type where each element carries a priority. Supports insert, getMin/getMax, and removeMin/removeMax. A heap is the standard implementation, but the ADT itself is just the interface. Think of it as a queue where cutting in line is the whole point.
Build heap
The process of turning an unordered array into a valid heap. The efficient approach runs heapifyDown on every internal node from the last internal node up to the root, achieving O(n) total time.
A binary heap is a complete binary tree that satisfies the heap ordering property
Two approaches to building a heap from an unsorted array:
Incremental (top-down): Insert elements one at a time, calling heapifyUp after each. Total cost: O(n log n)
Bottom-up (efficient): Start at the last internal node and call heapifyDown on each node moving toward the root. Total cost: O(n). This works because most nodes are near the bottom of the tree and have very little distance to sift down
The bottom-up approach is the one your exam will likely ask you to justify. The intuition: roughly half the nodes are leaves (no work), a quarter are one level up (sift down at most 1), an eighth are two levels up (sift down at most 2), and so on. The resulting sum converges to O(n)
Because a heap is a complete binary tree, it maps perfectly onto a flat array with no pointers and no wasted space
For a node at index i (0-indexed):
Parent: (i - 1) / 2 (integer division)
Left child: 2i + 1
Right child: 2i + 2
The root sits at index 0. The last element is at index n - 1
This representation gives excellent cache performance compared to pointer-based trees
Insert: Place the new element at the end of the array (the next open leaf position). Run heapifyUp from that position to restore the heap property. Time: O(log n)
Remove min/max: Copy the root (the min or max). Move the last element to the root position. Run heapifyDown from the root. Time: O(log n)
Peek (getMin/getMax): Return the root element. Time: O(1)
Build heap: Bottom-up heapifyDown from the last internal node to the root. Time: O(n)
The priority queue is the abstract interface; the heap is the concrete implementation
Core operations: insert (add an element with a priority), getMin/getMax (peek at the highest-priority element), removeMin/removeMax (extract it)
Priority queues show up in Dijkstra's shortest path, job scheduling, event-driven simulation, and Huffman coding
You can implement a priority queue with a sorted array or a linked list, but a heap gives the best balanced performance across all operations
Relationship | Formula |
|---|---|
Parent of node i | (i - 1) / 2 |
Left child of node i | 2i + 1 |
Right child of node i | 2i + 2 |
Last internal node | (n / 2) - 1 |
Operation | Time Complexity | Mechanism |
|---|---|---|
Insert | O(log n) | heapifyUp |
Delete min/max | O(log n) | heapifyDown |
Build heap (bottom-up) | O(n) | heapifyDown on internal nodes |
Build heap (incremental) | O(n log n) | heapifyUp on each insert |
Peek (min/max) | O(1) | Return root |
Priority queues built on heaps are the engine behind Dijkstra's shortest-path algorithm, which your satnav uses every time you ask for directions. Operating system schedulers use heaps to decide which process runs next, and streaming services use them to maintain top-K recommendation lists without sorting the entire catalogue.
Students often think build heap is O(n log n). It is not. The bottom-up heapifyDown approach is O(n). The O(n log n) figure applies only to the naive incremental approach (inserting one element at a time)
Students confuse heapifyUp and heapifyDown. heapifyUp is for insert (the new element rises). heapifyDown is for remove (the replacement sinks). Mixing them up on an exam costs easy marks
A heap is not a sorted array. The only guarantee is that the root is the min (or max). Siblings have no ordering relative to each other
Students sometimes assume a min-heap and a max-heap use the same heapifyDown logic. They do not: a min-heap swaps with the smaller child, a max-heap swaps with the larger child
Expect a question asking you to trace heapifyUp or heapifyDown on a specific array. Practise by hand
Build heap's O(n) runtime and its justification (the summation argument) is a common exam question
Know the array index formulas cold. Given an index, you should be able to name parent, left child, and right child instantly
Priority queue vs heap: the exam may ask you to distinguish the ADT from the implementation
True or false: Build heap using bottom-up heapifyDown runs in O(n log n) time.
Fill in the blank: The left child of a node at index i in a 0-indexed array is at index ____.
True or false: In a min-heap, sibling nodes are always in sorted order.
Fill in the blank: heapifyUp is used during ____, and heapifyDown is used during ____.
True or false: Peek (getMin) on a min-heap is O(log n).
Answers: 1. False (it is O(n)). 2. 2i + 1. 3. False (siblings have no ordering guarantee). 4. Insert; remove. 5. False (it is O(1)).
Q: You are given the array [15, 10, 20, 8, 12]. Show the result of building a min-heap using bottom-up heapifyDown.
A: Identify the last internal node (index 1, value 10). heapifyDown on index 1: 10 is less than 8 and 12, so swap 10 and 8. Array becomes [15, 8, 20, 10, 12]. Then heapifyDown on index 0: 15 is greater than 8 and 20, so swap 15 and 8. Array becomes [8, 15, 20, 10, 12]. Then heapifyDown continues on index 1: 15 is greater than 10, so swap. Final array: [8, 10, 20, 15, 12].
Q: Why is the bottom-up build heap O(n) rather than O(n log n)?
A: Most nodes are near the bottom of the tree and need to sift down only a small distance. Roughly n/2 nodes are leaves (0 swaps), n/4 nodes sift down at most 1 level, n/8 at most 2 levels, and so on. The sum n * (1/4 + 2/8 + 3/16 + ...) converges to O(n).
Q: Describe the steps to remove the minimum element from a min-heap stored in an array.
A: Copy the root (index 0) as the return value. Move the last element in the array to index 0. Decrement the heap size. Run heapifyDown from index 0: compare with both children, swap with the smaller child if the heap property is violated, and repeat until the element is in place or reaches a leaf.
Q: What is the difference between a priority queue and a heap?
A: A priority queue is an abstract data type that defines the operations (insert, getMin, removeMin). A heap is one concrete data structure that implements those operations efficiently. You could also implement a priority queue with a sorted array or a linked list, but a heap gives O(log n) insert and remove with O(1) peek.
This connects to graph algorithms because Dijkstra's shortest-path algorithm relies on a min-priority queue (typically a min-heap) to select the next vertex to process. It also connects to sorting: heapsort works by building a max-heap and then repeatedly extracting the max. If you are studying disjoint sets next, notice that both heaps and disjoint sets use tree structures stored cleverly in arrays.
heap, binary heap, min-heap, max-heap, priority queue, heapify, sift up, sift down, bubble up, percolate down, heapifyUp, heapifyDown, complete binary tree, build heap, heap sort, array-based tree, heap property, heap operations, DSA exam 4, data structures UIUC