Max-Heap | Engineering Interview Kit

Concept

A Max-Heap is fundamentally identical to a Min-Heap, with one simple reversed rule: Every Parent node must be strictly GREATER than or equal to its children.

This guarantees that the absolute largest item is always sitting at the Root (index 0).

Implementation Differences

To convert a Min-Heap implementation into a Max-Heap, you literally only have to change the comparison operators < and > in two places.

1. Bubble Up (Insertion):
Instead of swapping when the new item is smaller than the parent, you swap when the new item is larger than the parent.

// Min-Heap:
if (this.heap[index] >= this.heap[parentIndex]) break;

// Max-Heap:
if (this.heap[index] <= this.heap[parentIndex]) break;

2. Bubble Down (Deletion):
Instead of swapping with the smaller of the two children, you swap with the larger of the two children.

// Max-Heap Sink Down logic
let largestIndex = index;

if (leftChildIndex < length && this.heap[leftChildIndex] > this.heap[largestIndex]) {
    largestIndex = leftChildIndex;
}

if (rightChildIndex < length && this.heap[rightChildIndex] > this.heap[largestIndex]) {
    largestIndex = rightChildIndex;
}

The “Negative Number” Trick (Python / JS)

In Python, the heapq module only provides a Min-Heap out of the box. There is no native maxheapq.
In JavaScript, if you are using an external Priority Queue library, it might only support Min-Heaps by default.

The mathematical trick to instantly create a Max-Heap using a Min-Heap is to multiply all values by -1 before inserting them.

If you want a Max-Heap of [5, 10, 2]:

Insert -5.
Insert -10.
Insert -2.

Because -10 is mathematically the smallest number, the Min-Heap will dutifully bubble it to the absolute top!
When you pop() it out, you simply multiply it by -1 again to restore the original value: -1 * -10 = 10. You successfully retrieved the maximum value using a Min-Heap.

Interview Questions

Q: A problem asks you to continuously find the “Median” of a massive stream of numbers arriving in real-time. How do you solve this using Heaps?
A: This is LeetCode 295 (Find Median from Data Stream), one of the most famous Hard problems.
You use Two Heaps.

A Max-Heap to store the smaller half of the numbers.
A Min-Heap to store the larger half of the numbers.

When a new number arrives, you push it into the Max-Heap. Then, to ensure the halves remain balanced, you instantly pop the largest number from the Max-Heap and push it into the Min-Heap. (If the Min-Heap becomes larger than the Max-Heap, you pop the top of the Min-Heap back to the Max-Heap).
Because of this balancing act, the absolute middle numbers of the entire dataset are ALWAYS sitting right at the tops of the two heaps! To get the median in $O(1)$ time, you just look at the top of the Max-Heap (if odd length) or average the tops of both heaps (if even length).