Ugenz Academy/Tutorial

Heap

12 min read2,243 words

Reading progress

Keep learning

Heap

A Heap is a special type of complete binary tree that follows a specific ordering rule called the heap property.

Heaps are mainly used when we need to quickly access the smallest or largest element.

Heap = Complete Binary Tree + Heap Property

1. What is a Heap?

There are two main types:

Max Heap

The parent is greater than or equal to its children.

50 / \ 30 40 / \ / \ 10 20 25 35

For every node:

Parent >= Children

Therefore, the largest element is always at the root.

Maximum = 50

Min Heap

The parent is smaller than or equal to its children.

10 / \ 20 15 / \ / \ 30 40 25 35

For every node:

Parent <= Children

Therefore, the smallest element is always at the root.

Minimum = 10

2. Heap vs BST

This is very important because both use trees.

BST

50 / \ 30 70

Rule:

ALL values in left subtree < root ALL values in right subtree > root

Heap

Max Heap:

50 / \ 30 40

Rule:

Parent >= children

Notice that 30 and 40 don't have to be ordered relative to each other.

So:

BST is globally ordered, while Heap is only parent-child ordered.

3. Complete Binary Tree

A heap must be a complete binary tree.

A complete binary tree has:

  • Every level completely filled except possibly the last.
  • The last level is filled from left to right.

Example:

10 / \ 20 30 / \ / 40 50 60

This is complete.

But:

10 / \ 20 30 \ / 50 60

is not complete because the last level isn't filled from left to right.

4. Why Do We Use Complete Binary Trees?

Because a complete binary tree can be stored very efficiently inside an array.

For example:

10 / \ 20 30 / \ / \ 40 50 60 70

Can be stored as:

[10, 20, 30, 40, 50, 60, 70]

No pointers are required.

This is one of the most important ideas behind heaps.

5. Array Representation of Heap

For a 0-based array:

index = i

The formulas are:

Parent

parent = (i - 1) / 2

Left child

left = 2 * i + 1

Right child

right = 2 * i + 2

Example

Consider:

50 / \ 30 40 / \ / \ 10 20 25 35

Array:

Index: 0 1 2 3 4 5 6 Value: 50 30 40 10 20 25 35

For 50 at index 0:

Left child = 2(0) + 1 = 1 Right child = 2(0) + 2 = 2

So:

50 ├── index 1 → 30 └── index 2 → 40

For 30 at index 1:

Left child = 2(1)+1 = 3 Right child = 2(1)+2 = 4

Therefore:

30 ├── 10 └── 20

6. Max Heap

A Max Heap follows:

Parent >= Children

Example:

90 / \ 70 80 / \ / \ 40 50 60 30

The largest element is always:

root = 90

But notice:

70 and 80

are not necessarily sorted relative to each other.

That's okay.

7. Min Heap

A Min Heap follows:

Parent <= Children

Example:

10 / \ 20 15 / \ / \ 40 30 25 50

The smallest element is always:

root = 10

8. Heap Operations

The main heap operations are:

  1. Insert
  2. Get maximum/minimum
  3. Delete maximum/minimum
  4. Heapify
  5. Build heap
  6. Heap sort

The most important operations are:

Insert → O(log n) Delete root → O(log n) Get root → O(1)

9. Inserting Into a Heap

Let's create a Max Heap.

Start:

50

Insert:

30
50 / 30

Already valid.

Now insert:

40
50 / \ 30 40

Still valid.

Now insert:

60

First, because it must remain complete, put it at the next available position:

50 / \ 30 40 / 60

But:

60 > 30

So the heap property is violated.

We move 60 upward.

50 / \ 60 40 / 30

Now:

60 > 50

Still violated.

Move again:

60 / \ 50 40 / 30

Now the heap is valid.

This process is called:

Heapify Up / Bubble Up / Sift Up

10. Heapify Up

When inserting into a heap:

1. Add element at the end. 2. Compare it with its parent. 3. If heap property is violated, swap. 4. Continue upward.

For Max Heap:

if child > parent swap

For Min Heap:

if child < parent swap

Because the height of a complete binary tree is O(log n):

Insertion = O(log n)

11. Delete Root

Suppose we have a Max Heap:

90 / \ 70 80 / \ / \ 40 50 60 30

We want to remove the maximum element.

The maximum is at the root:

90

We cannot simply remove it because the tree structure must remain complete.

Instead:

Step 1

Move the last element to the root.

30 / \ 70 80 / \ / 40 50 60

Step 2

Now compare 30 with its children.

70 > 30 80 > 30

Take the larger child:

80

Swap:

80 / \ 70 30 / \ / 40 50 60

Again compare 30 with its children:

60 > 30

Swap:

80 / \ 70 60 / \ / 40 50 30

Now valid.

This process is called:

Heapify Down / Bubble Down / Sift Down

Therefore:

Delete root = O(log n)

12. Heapify Down

For a Max Heap:

1. Replace root with last element. 2. Compare with children. 3. Find the larger child. 4. Swap if child > parent. 5. Continue downward.

For a Min Heap:

Find the smaller child.

13. C++ Max Heap Using priority_queue

In C++, the easiest way to use a heap is:

#include <queue> priority_queue<int> pq;

By default:

priority_queue = Max Heap

Example:

#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; pq.push(50); pq.push(30); pq.push(70); pq.push(20); pq.push(90); cout << pq.top(); return 0; }

Output:

90

Because 90 is the maximum.

14. Main priority_queue Functions

Insert

pq.push(50);

Complexity:

O(log n)

Get maximum

pq.top();

Complexity:

O(1)

Remove maximum

pq.pop();

Complexity:

O(log n)

Check empty

pq.empty();

Number of elements

pq.size();

15. Min Heap in C++

By default:

priority_queue<int>

is a Max Heap.

To create a Min Heap:

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

Example:

#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>> pq; pq.push(50); pq.push(30); pq.push(70); pq.push(20); pq.push(90); cout << pq.top(); return 0; }

Output:

20

Because the smallest element is at the root.

16. Max Heap vs Min Heap

FeatureMax HeapMin Heap
RootLargestSmallest
Parent relationParent ≥ childrenParent ≤ children
C++ defaultYesNo
top()MaximumMinimum
InsertO(log n)O(log n)
Remove rootO(log n)O(log n)
Get rootO(1)O(1)

17. Heapify

Heapify means fixing a tree so that it satisfies the heap property.

For example:

30 / \ 50 40

For Max Heap, this is invalid because:

30 < 50

After heapify:

50 / \ 30 40

Heapify is commonly used during:

  • Insertion
  • Deletion
  • Building a heap
  • Heap sort

18. Building a Heap

Suppose we have:

[10, 30, 20, 5, 40, 50]

We can convert it into a heap.

There are two approaches:

Repeated insertion

Insert elements one by one.

Complexity:

O(n log n)

Bottom-up heap construction

Start from the last non-leaf node and heapify downward.

Complexity:

O(n)

This is an important DSA fact:

Building a heap using bottom-up heapify takes O(n), not O(n log n).

19. Leaf Nodes

In an array-based heap with n elements:

The leaf nodes start from approximately:

n / 2

For zero-based indexing, indices:

n/2 → n-1

are leaves.

Why?

Because these nodes don't have children.

Therefore, when building a heap, we don't need to heapify the leaves.

20. Heap Sort

Heap can also be used for sorting.

For ascending order, we can use a Max Heap.

Example:

Array: [40, 10, 30, 50, 20]

Build Max Heap:

50 / \ 40 30 / \ 10 20

Then repeatedly remove the maximum.

The elements become arranged in sorted order.

Heap Sort complexity:

Time = O(n log n) Space = O(1)

Heap Sort is therefore an important sorting algorithm.

You'll study sorting more deeply later in your roadmap.

21. Heap Applications

Heaps are extremely useful in real DSA problems.

1. Priority Queue

Example:

Emergency patients

The highest-priority patient should be processed first.

2. CPU Scheduling

Processes can have different priorities.

Process A → priority 5 Process B → priority 2 Process C → priority 10

A priority queue can select the highest priority.

3. Dijkstra's Algorithm

A min heap is commonly used to efficiently select the vertex with the smallest current distance.

You'll encounter this when studying:

Graphs

4. Top K Problems

Examples:

Top K largest numbers Top K smallest numbers Kth largest element Kth smallest element

Heaps are frequently used.

5. Merge K Sorted Lists

A min heap can efficiently select the smallest current element among multiple sorted lists.

22. Heap vs Stack vs Queue vs BST

StructureMain IdeaImportant Operation
StackLIFOTop
QueueFIFOFront
BSTOrdered treeSearch
Max HeapLargest at rootMaximum
Min HeapSmallest at rootMinimum

23. Heap vs BST

This is a common interview question.

BST

50 / \ 30 70 / \ / \ 20 40 60 80

Inorder:

20 30 40 50 60 70 80

It maintains an ordering among the entire subtrees.

Max Heap

80 / \ 50 70 / \ / \ 20 40 30 60

Only this needs to be true:

Parent >= Children

There is no requirement that the left subtree is smaller than the right subtree.

Therefore:

BST → good for searching ordered data Heap → good for repeatedly getting min/max

24. Important Heap Complexities

OperationComplexity
Get min/maxO(1)
InsertO(log n)
Delete rootO(log n)
HeapifyO(log n)
Build heapO(n)
Heap sortO(n log n)
Search arbitrary elementO(n)

Notice the last one.

A heap is not designed for fast arbitrary searching.

If you want to find 37 inside a heap, you may need to check many nodes.

25. Why Search is O(n) in a Heap

Consider:

100 / \ 50 80 / \ / \ 20 40 60 70

Suppose we search for:

60

Knowing that:

60 < 100

doesn't tell us exactly which subtree contains it.

Unlike a BST, the heap doesn't give us a left/right search direction.

Therefore:

Search = O(n)

26. A Simple Mental Model

Think about a company hierarchy.

Max Heap

The most important person is at the top:

CEO / \ Manager Manager

The parent has higher priority than the children.

Min Heap

The person with the smallest value/priority is at the top.

The key idea is:

Heap cares about priority, not complete sorting.

Final Summary

Remember these 7 points:

1. Heap is a Complete Binary Tree. 2. Two main types: Max Heap → largest at root Min Heap → smallest at root 3. Max Heap: Parent >= Children 4. Min Heap: Parent <= Children 5. Insert: Add at end → Heapify Up O(log n) 6. Delete root: Replace with last → Heapify Down O(log n) 7. Get root: O(1)

C++ shortcut

// Max Heap priority_queue<int> pq;
// Min Heap priority_queue<int, vector<int>, greater<int>> pq;

And the roadmap connection is:

Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy