Basics of Heap: Stop Searching, Start Understanding!

Harsh Jaiswal

7 min read

·

Oct 22, 2026

--

Listen

Share

A beginner-friendly guide to Min Heap, Max Heap, and the fundamentals of Heap in C++.

Today, I started revising the Heap data structure in DSA. I revised the fundamentals and solved three important LeetCode problems:

Last Stone Weight (1046),

Kth Largest Element in a Stream (703),

Kth Largest Element in an Array (215).

One of the best moments was solving LeetCode 215 in under 5 minutes during revision. It reminded me how understanding a pattern makes problem-solving much faster.

In this article, I’ll explain Heap fundamentals, followed by the approach and key learnings from each problem.

1. What Is a Heap?

A Heap is a Complete Binary Tree that follows a specific ordering property, called the Heap Property.

A Complete Binary Tree is a tree in which every level is completely filled except possibly the last level, which is filled from left to right.

There are two main types of heaps.

Min Heap

In a Min Heap, the parent node is always smaller than or equal to its children.

Example:

        10
       /  \
      20   15
     / \
    30  40

The smallest element, 10, is at the root.

Max Heap

In a Max Heap, the parent node is always greater than or equal to its children.

Example:

        50
       /  \
      30   40
     / \
    10  20

The largest element, 50, is at the root.

Important: A Heap is not a completely sorted tree. Only the parent-child ordering property is guaranteed.

2. Heap in C++ Using priority_queue

C++ provides a built-in priority_queue that makes heap operations convenient.

Max Heap

priority_queue<int> pq;

pq.push(10);
pq.push(30);
pq.push(20);cout << pq.top();  // 30

By default, priority_queue implements a Max Heap, so the largest element is available at the top.

Min Heap

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(10);
pq.push(30);
pq.push(20);cout << pq.top();  // 10

Using greater<int> creates a Min Heap, so the smallest element is available at the top.

Time Complexity

OperationComplexityInsert (push)O(log n)Access top (top)O(1)Remove top (pop)O(log n)

Heaps are especially useful when we repeatedly need the smallest or largest element without sorting the entire collection.

3. LeetCode 1046 — Last Stone Weight

Approach: Max Heap

We are given stones with different weights. In each operation, we select the two heaviest stones and smash them together.

• If both stones have the same weight, both are destroyed.
• If their weights differ, the remaining stone has the difference in weight.
• We repeat until at most one stone remains.

Since we always need the two heaviest stones, a Max Heap is the perfect choice.

Real-Life Analogy: A Boxing Match Between the Two Strongest Players

Imagine a competition in which players have different strength levels.

In every round, the two strongest players compete:

• If both have equal strength, both are eliminated.
• If one is stronger, the weaker player is eliminated, and the stronger player loses strength equal to the weaker player’s strength.
• The remaining player returns to the competition.

We repeat this process until at most one player remains.

This is exactly the idea behind Last Stone Weight.

Since we always need the two heaviest stones, a Max Heap is the right choice.

Example

stones = [2, 7, 4, 1, 8, 1]

Initially, the heaviest stones are 8 and 7.

Round 1:

8 vs 7 → Remaining weight = 1

The remaining stone weighs 1.

Now the stones effectively become:

[2, 4, 1, 1, 1]

Round 2:

4 vs 2 → Remaining weight = 2

Remaining stones:

[2, 1, 1, 1]

Round 3:

2 vs 1 → Remaining weight = 1

Remaining stones:

[1, 1, 1]

Round 4:

1 vs 1 → Both destroyed

One stone of weight 1 remains.

Final Answer: 1

Press enter or click to view image in full size

Dry Run

Suppose:

stones = [2, 7, 4, 1, 8, 1]

The two heaviest stones are selected in each round.

OperationResult8 and 714 and 222 and 111 and 1Both destroyed

The remaining stone has weight 1.

Complexity

• Time: O(n log n)
• Space: O(n)

Key learning: When a problem repeatedly asks for the maximum element, think of a Max Heap.

4. LeetCode 703 — Kth Largest Element in a Stream

Approach: Min Heap of Size K

We need to find the Kth largest element as new numbers arrive in a stream.

Instead of storing every element in a sorted collection, we maintain a Min Heap containing only the K largest elements seen so far.

The smallest element among those K elements will be the Kth largest overall.

Real-Life Analogy: Maintaining the Top 3 Students in a School

Imagine a school where students keep receiving new exam scores.

You don’t need the complete ranking of every student. You only need to know the third-highest score at any moment.

Suppose the scores arriving are:

4, 5, 8, 2

And we need the third-largest score, so k = 3.

The three highest scores are:

4, 5, 8

The third-largest score is 4.

Now a new student arrives with a score of 10.

The three highest scores become:

5, 8, 10

The third-largest score is now 5.

Notice that we don’t need to maintain every score in sorted order. We only need the top three.

Why Use a Min Heap?

We maintain a Min Heap of size k.

Think of it as a leaderboard that can hold only three students.

Whenever a new score arrives:

1. Add the score to the heap.
2. If more than three scores are present, remove the smallest.
3. The top of the heap is the third-largest score.

Why Min Heap? Because the smallest score among the top three is exactly the third-largest overall.

Press enter or click to view image in full size

Dry Run

Suppose k = 3 and the stream is:

[4, 5, 8, 2]

After processing these numbers, the three largest elements are 4, 5, 8.

The Min Heap’s top is 4, which is the third-largest element.

Now, a new value 10 arrives.

Before: [4, 5, 8]
Add: 10
Remove smallest: 4

After: [5, 8, 10]

The third-largest element is now 5.

Complexity

• Initialization: O(n log k) with repeated insertion.
• Each add() operation: O(log k)
• Auxiliary space: O(k)

Key learning: When the input keeps changing and you need the Kth largest element, maintain a Min Heap of size K.

5. LeetCode 215 — Kth Largest Element in an Array

Approach: Min Heap of Size K

This problem looks similar to LeetCode 703, but there is an important difference: here, the entire array is available at once.

We need to return the Kth largest element without necessarily sorting the entire array.

The same pattern works:

1. Insert each number into a Min Heap.
2. If the heap size exceeds K, remove the smallest element.
3. After processing every number, the heap contains the K largest elements.
4. The top element is the Kth largest.

Real-Life Analogy: Finding the Second-Highest Bid in an Auction

Imagine an auction with bids:

[3, 2, 1, 5, 6, 4]

You need to find the second-highest bid.

One approach would be to sort every bid and then select the second element.

But do you really need to sort every bid if you only care about the top two?

No!

We can maintain just the two highest bids using a Min Heap of size 2.

Step-by-Step Example

Here, k = 2.

Initially, the heap is empty.

Bid 1: 3

Heap: [3]

Bid 2: 2

Heap: [2, 3]

We have the two largest bids so far. The smallest of them is 2.

Bid 3: 1

Insert 1 → [1, 3, 2]
Remove the smallest → [2, 3]

The bid 1 is too small to remain in the top two.

Bid 4: 5

Insert 5 → [2, 3, 5]
Remove the smallest → [3, 5]

Bid 5: 6

Insert 6 → [3, 5, 6]
Remove the smallest → [5, 6]

Bid 6: 4

Insert 4 → [4, 5, 6]
Remove the smallest → [5, 6]

The final two largest bids are 5 and 6.

The smallest of these two is 5, so the second-largest bid is 5.

Final Answer: 5

Press enter or click to view image in full size

Complexity

• Time: O(n log k)
• Auxiliary space: O(k)

My Revision Milestone

I solved this problem in under 5 minutes during my Heap revision.

For me, the important part wasn’t just writing the code quickly. It was recognizing the pattern immediately:

Kth Largest → Min Heap of Size K.

When the pattern becomes familiar, the solution becomes much more straightforward.

Quick Revision Rules

• Need the maximum repeatedly? Use a Max Heap.
• Need the minimum repeatedly? Use a Min Heap.
• Need the K largest elements? Use a Min Heap of size K.
• Need the K smallest elements? Use a Max Heap of size K.
• Need to process incoming values? Consider maintaining a bounded heap.

Conclusion

Revising Heap today reinforced an important lesson: DSA is not just about memorizing solutions; it’s about recognizing patterns.

Starting with Heap fundamentals and applying them to three LeetCode problems helped me connect the concepts with real interview-style questions.

I’ll continue practicing more Heap patterns, including Top K Frequent Elements, K Closest Points, Merge K Sorted Lists, and Median from Data Stream.

One step at a time, one pattern at a time. 🚀

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#BasicsOfHeap #DSA #CodingInterview #EnjoyProblems