Data Structures
Heaps & Priority Queue
Difficulty: Intermediate
Pull the next task in priority order from a stream of millions, and a sorted array gives you O(1) extract but O(n) insert; a sorted linked list flips the costs but stays linear; a balanced BST hits O(log n) for both but with substantial...
Heaps & Priority Queue
Pull the next task in priority order from a stream of millions, and a sorted array gives you O(1) extract but O(n) insert; a sorted linked list flips the costs but stays linear; a balanced BST hits O(log n) for both but with substantial pointer overhead. A Heap quietly outperforms all three for this exact workload by storing a complete binary tree in a flat array and keeping just the min (or max) at the root.
This lesson covers the heap property, the parent-and-child index formulas (parent = (i-1)/2, left = 2i+1, right = 2i+2) that let array indices encode tree structure with no pointers, sift-up and sift-down for O(log n) insert and extract, and the linear-time heapify build. You will see how this maps onto the priority queue abstraction and onto interview staples such as top-K elements, K-th largest, merge K sorted lists, and the streaming median with two heaps; on the systems side, the same structure powers Dijkstra and Prim.
In Trees: Binary Tree Fundamentals, you saw what a complete binary tree is and how to traverse one; the heap reuses that exact shape but stores it implicitly. Arrays & Strings is what makes the implicit storage cheap: a flat array gives O(1) parent and child access through arithmetic, with no allocations per node.
Next, Binary Search Tree (BST) trades the heap's partial ordering for a full ordering invariant, unlocking sorted iteration and key-based search at the cost of needing actual pointers.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the complete binary tree property and how it enables array-based storage without pointers.
Define min-heap and max-heap properties and identify which one a given array represents.
Derive and apply the parent/child index formulas for array-based heaps.
Implement insert (sift up) and extractMin/extractMax (sift down) operations with correct O(log n) complexity.
Build a heap from an unsorted array using the bottom-up heapify algorithm in O(n) time.
Use heaps as the underlying structure for a priority queue and identify real-world applications.
Why This Matters
01
Heaps are the backbone of the priority queue abstraction -- the most efficient way to repeatedly access the smallest or largest element, which appears in scheduling, event-driven simulations, and operating system task management.
02
Interview problems involving 'top-K elements,' 'Kth largest,' 'merge K sorted lists,' and 'median from a data stream' all require heap knowledge, making this one of the most tested intermediate data structures.
03
Graph algorithms like Dijkstra's shortest path and Prim's minimum spanning tree rely on a priority queue (min-heap) to efficiently select the next vertex to process.
04
Understanding how a complete binary tree maps to an array via index formulas deepens your grasp of implicit data structures -- structures that encode relationships through position rather than pointers.
Key Terms
8 terms you'll encounter in this lesson
Heap
A complete binary tree stored in an array where every node satisfies the heap property: in a min-heap every parent is smaller than or equal to its children; in a max-heap every parent is larger than or equal to its children.
Min-heap
A heap where the smallest element is always at the root (index 0). Every parent node has a value less than or equal to its children.
Max-heap
A heap where the largest element is always at the root (index 0). Every parent node has a value greater than or equal to its children.
Sift up (bubble up)
After inserting at the end of the heap array, repeatedly swap the new element with its parent until the heap property is restored. Runs in O(log n).
Sift down (bubble down)
After placing the last element at the root (during extract), repeatedly swap it with its smallest (min-heap) or largest (max-heap) child until the heap property is restored. Runs in O(log n).
Heapify
Building a heap from an unordered array by calling sift down on every non-leaf node from the bottom up. Runs in O(n), not O(n log n), because most nodes are near the leaves and sift down a short distance.
Priority queue
An abstract data type where each element has a priority. The element with the highest priority (smallest value in a min-priority queue) is dequeued first. Typically implemented with a binary heap.
Complete binary tree
A binary tree where every level is fully filled except possibly the last, which is filled from left to right. This shape guarantees the tree can be stored in a contiguous array without gaps.
Heads Up
Common misconceptions to watch out for
"A heap is a sorted array"
A heap only guarantees a partial ordering: each parent is smaller (or larger) than its children. Siblings have no ordering relationship. For example, [1, 3, 2, 7, 5] is a valid min-heap even though 3 > 2.
"Building a heap from an array is O(n log n)"
Inserting n elements one by one is O(n log n), but the bottom-up heapify algorithm is O(n). The key insight is that most nodes are near the bottom of the tree and sift down only a short distance.
"A heap and a BST are the same thing"
A BST guarantees left < parent < right (full ordering), enabling O(log n) search. A heap only guarantees parent <= children (partial ordering), so searching for an arbitrary element is O(n). Heaps excel at finding the min/max in O(1), which a BST cannot do unless it tracks the leftmost/rightmost node.
"Python's heapq supports max-heaps natively"
Python's heapq module only supports min-heaps. To simulate a max-heap, negate all values before pushing and negate again after popping: push -x, pop gives -max.