Module 19: Heap

Learning Objectives

By the end of this module, you will be able to:

• Understand what a Heap is and how it differs from other tree structures.
• Learn Max Heap and Min Heap.
• Understand the Heapify operation.
• Implement a Priority Queue using a Heap.
• Learn the Heap Sort algorithm.
• Solve problems like K Largest Elements and Merge K Sorted Arrays.
• Analyze the time complexity of heap operations.

Introduction

A Heap is a special type of Complete Binary Tree that satisfies the Heap Property.

Unlike a Binary Search Tree (BST), a heap does not maintain sorted order. Instead, it ensures that the parent node is either greater than or smaller than its children, depending on the heap type.

Heaps are widely used in:

• Priority Queues
• Operating Systems
• CPU Scheduling
• Dijkstra's Algorithm
• Prim's Algorithm
• Heap Sort
• Task Scheduling
• Event Simulation

What is a Heap?

A Heap is a Complete Binary Tree, meaning:

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

Example

textCopy
1           50
2         /    \
3       30      40
4      /  \    /
5    10   20  35

Array Representation

textCopy
1Index
2
30   1   2   3   4   5
4
5Value
6
750  30  40  10  20  35

Unlike linked trees, heaps are usually stored in arrays.

Heap Properties

Every heap satisfies one of the following:

• Max Heap Property
• Min Heap Property

Max Heap

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

Example

textCopy
1          90
2        /    \
3      70      60
4     /  \    / \
5   30   20  40 10

Properties

• Largest element is always at the root.
• Fast access to the maximum value.

Applications

• Priority Queue
• Task Scheduling
• Heap Sort

Min Heap

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

Example

textCopy
1          10
2        /    \
3      20      30
4     /  \    / \
5   40   50  60 70

Properties

• Smallest element is always at the root.
• Efficient retrieval of the minimum value.

Applications

• Dijkstra's Algorithm
• Prim's Algorithm
• Event Scheduling

Array Representation of Heap

For a node at index i:

textCopy
1Left Child  = 2 * i + 1
2
3Right Child = 2 * i + 2
4
5Parent      = (i - 1) / 2

Example

textCopy
1Index
2
30  1  2  3  4  5
4
5Value
6
750 30 40 10 20 35

For index 1

textCopy
1Parent = 50
2
3Left Child = 10
4
5Right Child = 20

Heap Node Relationships

Max Heap Implementation

cCopy
1#include <stdio.h>
2
3#define SIZE 100
4
5int heap[SIZE];
6int size = 0;
7
8void insert(int value)
9{
10    int i = size++;
11
12    while(i > 0 && heap[(i - 1) / 2] < value)
13    {
14        heap[i] = heap[(i - 1) / 2];
15        i = (i - 1) / 2;
16    }
17
18    heap[i] = value;
19}
20
21void display()
22{
23    for(int i = 0; i < size; i++)
24        printf("%d ", heap[i]);
25
26    printf("\n");
27}
28
29int main()
30{
31    insert(50);
32    insert(30);
33    insert(70);
34    insert(20);
35
36    display();
37
38    return 0;
39}

Output

textCopy
170 30 50 20

Heapify

Heapify is the process of restoring the heap property after insertion, deletion, or replacement.

Example

Before Heapify

textCopy
1        20
2       /  \
3     50    40

After Heapify

textCopy
1        50
2       /  \
3     20    40

Max Heapify Program

cCopy
1void heapify(int arr[], int n, int i)
2{
3    int largest = i;
4
5    int left = 2 * i + 1;
6    int right = 2 * i + 2;
7
8    if(left < n && arr[left] > arr[largest])
9        largest = left;
10
11    if(right < n && arr[right] > arr[largest])
12        largest = right;
13
14    if(largest != i)
15    {
16        int temp = arr[i];
17        arr[i] = arr[largest];
18        arr[largest] = temp;
19
20        heapify(arr, n, largest);
21    }
22}

Time Complexity

textCopy
1O(log n)

Heap Insertion

Steps

1. Insert at the last position.
2. Compare with the parent.
3. Swap if necessary.
4. Continue until the heap property is restored.

Example

Insert 80

textCopy
1Before
2
370 50 40 30

textCopy
1After
2
380 70 40 30 50

Time Complexity

textCopy
1O(log n)

Heap Deletion

Deleting the root node involves:

1. Replace the root with the last element.
2. Remove the last node.
3. Apply Heapify.

Example

Before

textCopy
180
270
360
450
540

After deleting 80

textCopy
170
250
360
440

Time Complexity

textCopy
1O(log n)

Priority Queue

A Priority Queue processes elements according to priority instead of insertion order.

Heap is the most common implementation.

Example

textCopy
1Priority
2
3Task A (3)
4
5Task B (1)
6
7Task C (2)

Execution Order

textCopy
1Task B
2
3Task C
4
5Task A

Applications

• CPU Scheduling
• Hospital Management
• Event Simulation
• Network Routing

Heap Sort

Heap Sort is an efficient comparison-based sorting algorithm.

Algorithm

1. Build a Max Heap.
2. Swap the root with the last element.
3. Reduce heap size.
4. Heapify the root.
5. Repeat until sorted.

Visualization

textCopy
1Input
2
340 10 30 20 50
4
5↓
6
7Build Max Heap
8
9↓
10
11Swap Root
12
13↓
14
15Heapify
16
17↓
18
19Sorted Array

Heap Sort Program

cCopy
1#include <stdio.h>
2
3void heapify(int arr[], int n, int i)
4{
5    int largest = i;
6
7    int left = 2 * i + 1;
8    int right = 2 * i + 2;
9
10    if(left < n && arr[left] > arr[largest])
11        largest = left;
12
13    if(right < n && arr[right] > arr[largest])
14        largest = right;
15
16    if(largest != i)
17    {
18        int temp = arr[i];
19        arr[i] = arr[largest];
20        arr[largest] = temp;
21
22        heapify(arr, n, largest);
23    }
24}
25
26void heapSort(int arr[], int n)
27{
28    for(int i = n / 2 - 1; i >= 0; i--)
29        heapify(arr, n, i);
30
31    for(int i = n - 1; i > 0; i--)
32    {
33        int temp = arr[0];
34        arr[0] = arr[i];
35        arr[i] = temp;
36
37        heapify(arr, i, 0);
38    }
39}

Time Complexity

Space Complexity

textCopy
1O(1)

Heap vs Binary Search Tree

Practice Project 1: K Largest Elements

Problem

Find the largest K elements from an array.

Example

Input

textCopy
110 20 15 30 40 50
2
3K = 3

Output

textCopy
150
2
340
4
530

Approach

• Build a Max Heap.
• Remove the maximum element K times.

Time Complexity

textCopy
1O(n + k log n)

Applications

• Leaderboards
• Top K Search Results
• Analytics

Practice Project 2: Merge K Sorted Arrays

Problem

Merge multiple sorted arrays into one sorted array.

Example

textCopy
1Array 1
2
31 4 7
4
5Array 2
6
72 5 8
8
9Array 3
10
113 6 9

Output

textCopy
11 2 3 4 5 6 7 8 9

Approach

• Insert the first element of each array into a Min Heap.
• Remove the minimum element.
• Insert the next element from the same array.
• Repeat until all arrays are merged.

Time Complexity

textCopy
1O(N log K)

Where:

• N = Total number of elements
• K = Number of arrays

Applications

• External Sorting
• Database Systems
• Search Engines
• File Merging

Real-World Applications of Heaps

CPU Scheduling

The operating system selects the highest-priority process first.

textCopy
1Priority Queue
2
3↓
4
5Heap
6
7↓
8
9CPU

Dijkstra's Algorithm

Min Heaps efficiently select the next node with the smallest distance.

Event Simulation

Events are processed based on the earliest scheduled time.

Task Scheduling

Cloud platforms and operating systems prioritize jobs using heaps.

Heap Sort

Heaps provide a guaranteed O(n log n) sorting algorithm without additional memory.

Common Interview Questions

1. What is a Heap?
2. Difference between Max Heap and Min Heap.
3. Explain Heapify.
4. Implement Heap Sort.
5. Build a Heap from an Array.
6. Find the K Largest Elements.
7. Merge K Sorted Arrays.
8. Difference between Heap and BST.
9. Implement a Priority Queue using a Heap.
10. Find the Kth Smallest Element using a Heap.

Common Mistakes to Avoid

• Confusing a heap with a Binary Search Tree.
• Forgetting to call heapify() after deleting the root.
• Using incorrect parent or child index formulas.
• Assuming heap traversal produces sorted output.
• Ignoring heap size updates during insertion and deletion.
• Accessing child indices outside the array bounds.

Best Practices

• Store heaps in arrays to avoid pointer overhead.
• Use a Max Heap when frequent access to the largest element is required.
• Use a Min Heap when frequent access to the smallest element is required.
• Always restore the heap property after insertion or deletion.
• Use heapify() efficiently when building a heap from an array.
• Prefer heaps over full sorting when only the top K elements are needed.

Module Summary

In this module, you learned:

• What a Heap is and why it is implemented as a complete binary tree.
• The differences between Max Heap and Min Heap.
• How heaps are represented using arrays.
• How Heapify restores the heap property after updates.
• How to implement Priority Queues using heaps.
• How the Heap Sort algorithm works and why it guarantees O(n log n) time complexity.
• Practical applications such as finding the K Largest Elements and Merging K Sorted Arrays.
• Real-world uses of heaps in scheduling, graph algorithms, event simulation, and search systems.

After completing this module, you'll be ready to learn Graphs, where you'll study graph representations, Breadth-First Search (BFS), Depth-First Search (DFS), shortest path algorithms, minimum spanning trees, topological sorting, and graph traversal techniques.