Back to Study Material Data Structures and Algorithms

Min Heap and Max Heap

A min-heap and a max-heap differ only in the direction of their heap property. In a min-heap, the parent is always less than or equal to its children, so t...

Min Heap and Max Heap

Distinguishing Min-Heap from Max-Heap

A min-heap and a max-heap differ only in the direction of their heap property. In a min-heap, the parent is always less than or equal to its children, so the root holds the global minimum. In a max-heap, the parent is always greater than or equal to its children, so the root holds the global maximum. Every operation — insert, sift-up, sift-down — is identical in structure; only the comparison operator flips.

Both variants are complete binary trees stored in arrays. The minimum-element access in a min-heap and maximum-element access in a max-heap are O(1) since the answer is always the root at index zero. Insertion and extraction are both O(log N). These asymmetric access costs make heaps ideal for priority queues where you need fast access to one extreme but can tolerate slower access to the other.

A common pattern uses both a min-heap and a max-heap simultaneously to maintain a running median of a data stream. The max-heap holds the lower half of seen values and the min-heap holds the upper half. The median is always available at the roots of the two heaps in O(1) time, and each insertion is O(log N).

Implementing Both Variants and Conversion

In most programming languages, a standard library provides only one variant. In Python, heapq is a min-heap. To simulate a max-heap, negate all values before insertion and negate again after extraction. In Java, PriorityQueue is a min-heap by default but accepts a custom comparator to function as a max-heap. In C++, priority_queue is a max-heap by default.

Converting an array to a min-heap or max-heap is done with the O(N) build-heap procedure. Converting a min-heap to a max-heap (or vice versa) is not simply a pointer reversal — you must rebuild entirely in O(N) because the internal structure differs. However, extracting all elements from one heap and inserting into the other is O(N log N), which is less efficient than rebuilding.

To merge two heaps of sizes M and N, you cannot simply combine their arrays without rebuilding. Merging and rebuilding runs in O(M plus N). Mergeable heaps like binomial heaps and Fibonacci heaps support merge in O(log N) or O(1) amortized time respectively, but at significant implementation complexity.

Worked Example: K-th Largest Element

Worked example: find the k-th largest element in an unsorted array of N integers using a min-heap of size k. Initialize an empty min-heap. Iterate through the array: for each element, push it into the heap. If the heap size exceeds k, pop the smallest element. After processing all N elements, the heap contains the k largest elements and its root is the k-th largest. For N equals ten and k equals three with array [3, 2, 1, 5, 6, 4], after processing: heap retains [4, 5, 6], root is 4, which is the third largest.

Time complexity is O(N log K). Space complexity is O(K). If K is much smaller than N, this is significantly better than sorting the array in O(N log N) with O(N) space.

Interview tip: clearly distinguish when to use a min-heap versus a max-heap for a given problem. To find the k largest elements, use a min-heap of size k (so you discard small elements). To find the k smallest elements, use a max-heap of size k (so you discard large elements). Getting this direction wrong is a very common interview mistake, so rehearse the reasoning until it is automatic.