What is a Binary Heap?
A binary heap is a complete binary tree that satisfies the heap property. In a min heap, every parent node is smaller than or equal to its children, so the root is always the minimum. In a max heap, every parent is greater than or equal to its children, making the root the maximum.
Despite being visualized as a tree, a binary heap is stored as a flat array. For any node at index i:
- •Parent:
floor((i - 1) / 2) - •Left child:
2i + 1 - •Right child:
2i + 2
This array representation is what makes heaps efficient , no pointers needed, and cache locality is excellent.
Heap Operations & Time Complexity
| Operation | Time | Description |
|---|---|---|
| Insert | O(log n) | Add element at the end, then sift up to restore the heap property. |
| Extract Min/Max | O(log n) | Remove the root, move last element to root, then sift down. |
| Peek | O(1) | Return the root element without removing it. |
| Build Heap | O(n) | Floyd's bottom-up heapify. Faster than n individual inserts. |
| Heapify (sift) | O(log n) | Restore heap property for a single node by sifting up or down. |
Insert (sift up)
A new element is placed at the next available position (end of the array) to maintain the complete tree shape. Then it “sifts up” , repeatedly compared with its parent and swapped if it violates the heap property , until it finds its correct position. At most log n swaps.
Extract Min / Max (sift down)
The root (min or max) is removed. The last element in the array takes its place, then “sifts down” , compared with its children and swapped with the smaller (min heap) or larger (max heap) child , until the heap property is restored. Also at most log n swaps.
Build Heap , O(n), not O(n log n)
A common interview question: why is building a heap O(n)? Using Floyd's bottom-up approach, we start from the last non-leaf node and sift down. Leaf nodes (half the tree) need 0 work. Nodes one level above need at most 1 swap. The sum converges to O(n), which is tighter than the O(n log n) you'd get from n individual inserts.
Min Heap vs Max Heap
The only difference is the comparison direction. In a min heap, the smallest element is at the root and parents are always ≤ children. In a max heap, the largest is at the root and parents are always ≥ children.
Most language standard libraries default to one type: Python's heapq is a min heap. Java's PriorityQueue is also a min heap by default. To get a max heap in Python, negate the values. In Java, pass Collections.reverseOrder().
Common Interview Questions Using Heaps
Heaps appear frequently in coding interviews. Key problem patterns:
- •Top K elements , Use a min heap of size K. Push every element; if size exceeds K, pop. The heap holds the K largest.
- •Merge K sorted lists , Push the head of each list into a min heap. Pop the smallest, push its next node. Repeat.
- •Median of a stream , Maintain a max heap (left half) and a min heap (right half). Balance sizes after each insert.
- •Dijkstra's shortest path , Use a min heap as the priority queue to always expand the nearest unvisited node.
- •Task scheduler , Use a max heap to always schedule the most frequent remaining task first.
- •Kth largest in a stream , Maintain a min heap of size K. The root is always the Kth largest.
Frequently Asked Questions
What is a binary heap?add
A binary heap is a complete binary tree stored as an array that satisfies the heap property: in a min heap every parent is smaller than its children, and in a max heap every parent is larger. It's the standard implementation for priority queues.
What is the difference between a min heap and a max heap?add
In a min heap, the root is the smallest element and every parent node is less than or equal to its children. In a max heap, the root is the largest element and every parent is greater than or equal to its children. The operations are identical , only the comparison direction changes.
Why is building a heap O(n) instead of O(n log n)?add
Building a heap using Floyd's algorithm (bottom-up heapify) is O(n) because most nodes are near the bottom of the tree and require very few swaps. Leaf nodes need 0 swaps, nodes one level above need at most 1, and so on. The mathematical sum converges to O(n), not O(n log n).
How is a binary heap stored in an array?add
A binary heap is stored in a zero-indexed array where for any node at index i: the parent is at index floor((i-1)/2), the left child is at index 2i+1, and the right child is at index 2i+2. This compact representation avoids pointers entirely.
When should you use a heap in a coding interview?add
Use a heap when you need to repeatedly find or remove the minimum/maximum element: top-K problems, merge K sorted lists, median of a stream, Dijkstra's shortest path, task scheduling, and any problem involving a priority queue.