Articles / DSA · Part 19

Heaps: Representation and Implementation of Priority Queues

Learn how Min Heaps and Max Heaps work, how Binary Heaps are represented using arrays, and how insertion and deletion maintain the Heap Property with C examples.

Heaps: Representation and Implementation of Priority Queues

In the previous article, we learned about Priority Queues, where elements are processed according to their priority.

But how can we efficiently find and remove the highest-priority element?

One commonly used data structure for this purpose is a Heap.

A Heap helps us access the smallest or largest element quickly, making it useful for implementing Priority Queues.

1. What Is a Heap?

A Heap is a special type of tree-based data structure that follows a specific ordering rule.

A Binary Heap has two important properties:

  • Complete Binary Tree: All levels are completely filled except possibly the last, which is filled from left to right.
  • Heap Property: The parent and child elements must follow a particular order.

<abbr title=”A tree in which every level is full except possibly the last, and the last level is filled from left to right.”>Complete Binary Tree</abbr>

There are two main types of Binary Heaps:

  1. Min Heap
  2. Max Heap

2. Types of Heaps

A. Min Heap

In a Min Heap, the value of every parent is smaller than or equal to the values of its children.

Therefore, the smallest element is always at the root (topmost element).

Example:

          10
         /  \
       20    15
      / \    /
    30  40  25

Here:

  • 10 is smaller than 20 and 15.
  • 20 is smaller than 30 and 40.
  • 15 is smaller than 25.

The smallest element, 10, is at the root.

B. Max Heap

In a Max Heap, the value of every parent is greater than or equal to the values of its children.

Therefore, the largest element is always at the root.

Example:

          50
         /  \
       30    40
      / \    /
    10  20  25

Here, 50 is the largest element and is at the root.

Remember:

  • Min Heap → Smallest element at the root.
  • Max Heap → Largest element at the root.

The remaining elements do not need to be arranged in fully sorted order. They only need to follow the Heap Property.

3. How Is a Heap Represented?

Although we draw a Heap like a tree, it is usually stored in an array.

Let’s take this Min Heap:

          10
         /  \
       20    15
      / \    /
    30  40  25

Its array representation is:

Index:   0   1   2   3   4   5
Value:  10  20  15  30  40  25

The elements are stored level by level, from left to right.

Since a Binary Heap is a Complete Binary Tree, we can easily find the parent and children of any element using its array index.

Important Index Formulas

Suppose an element is stored at index i:

Relationship Formula
Parent (i - 1) / 2
Left Child 2 * i + 1
Right Child 2 * i + 2

Example:

Consider the element 20, which is at index 1.

  • Parent index = (1 - 1) / 2 = 0
  • Left child index = 2 * 1 + 1 = 3
  • Right child index = 2 * 1 + 2 = 4

Therefore:

  • Parent = 10
  • Left child = 30
  • Right child = 40

These formulas make array-based Heap implementation straightforward.

4. Basic Operations on a Heap

Let’s understand the two most important operations: insertion and deletion.

We’ll use a Min Heap for both examples.

A. Insertion

When we insert a new element, it is first placed in the next available position to maintain the Complete Binary Tree structure.

Then, we compare it with its parent.

If it is smaller than its parent, we swap their positions. We continue until the Heap Property is restored.

This process is called <abbr title=”Moving a newly inserted element upward by swapping it with its parent until the Heap Property is restored.”>Heapify Up</abbr> or Sift Up.

Example:

Consider the existing Min Heap:

          10
         /  \
       20    15
      / \
    30  40

Now, insert 5.

Step 1: Place 5 in the next available position.

          10
         /  \
       20    15
      / \    /
    30  40  5

Step 2: Compare 5 with its parent, 15.

Since 5 is smaller, swap them.

          10
         /  \
       20    5
      / \    /
    30  40  15

Step 3: Compare 5 with its new parent, 10.

Since 5 is smaller, swap again.

           5
         /   \
       20     10
      / \     /
    30  40   15

Now the Heap Property is restored.

B. Deletion

In a Heap, the standard deletion operation removes the root element.

In a Min Heap, it removes the smallest element. In a Max Heap, it removes the largest element.

Let’s remove the root from this Min Heap:

          5
         /  \
       20    10
      / \    /
    30  40  15

Step 1: Remove the root element, 5.

Step 2: Move the last element, 15, to the root position.

          15
         /  \
       20    10
      / \
    30  40

Step 3: Compare 15 with its children, 20 and 10.

Since 10 is the smallest, swap 15 and 10.

          10
         /  \
       20    15
      / \
    30  40

Now the Heap Property is restored.

This process is called <abbr title=”Moving an element downward by swapping it with the smaller child in a Min Heap, or the larger child in a Max Heap, until the Heap Property is restored.”>Heapify Down</abbr> or Sift Down.

5. C Implementation of a Min Heap

Let’s implement a Min Heap using an array.

We’ll include three basic operations:

  • Insert: Adds a new element.
  • Extract Min: Removes and returns the smallest element.
  • Display: Prints the Heap elements.
#include <stdio.h>

#define SIZE 100

int heap[SIZE];
int n = 0;

void insert(int value) {
    if (n == SIZE) {
        printf("Heap is full\n");
        return;
    }

    int i = n;
    heap[i] = value;
    n++;

    // Heapify Up
    while (i > 0) {
        int p = (i - 1) / 2;

        if (heap[p] <= heap[i])
            break;

        int temp = heap[p];
        heap[p] = heap[i];
        heap[i] = temp;

        i = p;
    }
}

int extractMin() {
    if (n == 0) {
        printf("Heap is empty\n");
        return -1;
    }

    int min = heap[0];

    heap[0] = heap[n - 1];
    n--;

    // Heapify Down
    int i = 0;

    while (1) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if (left < n &&
            heap[left] < heap[smallest])
            smallest = left;

        if (right < n &&
            heap[right] < heap[smallest])
            smallest = right;

        if (smallest == i)
            break;

        int temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;

        i = smallest;
    }

    return min;
}

void display() {
    for (int i = 0; i < n; i++)
        printf("%d ", heap[i]);

    printf("\n");
}

int main() {
    insert(30);
    insert(10);
    insert(20);
    insert(5);
    insert(15);

    printf("Min Heap: ");
    display();

    printf("Removed: %d\n", extractMin());

    printf("After deletion: ");
    display();

    return 0;
}

Output:

Min Heap: 5 10 20 30 15
Removed: 5
After deletion: 10 15 20 30

Notice that the array does not appear fully sorted. It only follows the Min Heap Property.

6. Time Complexity of Heap Operations

A Heap allows us to perform important operations efficiently.

Operation Time Complexity
Access Min/Max (Root) O(1)
Insertion O(log n)
Deletion of Root O(log n)
Searching for an element O(n)

Why does insertion and deletion take O(log n)?

Because a Heap is a Complete Binary Tree, its height grows logarithmically as the number of elements increases.

An element may move from the bottom to the root during insertion, or from the root towards the bottom during deletion. Therefore, these operations take O(log n) time.

7. Applications of Heaps

Heaps are useful in several areas:

  • Priority Queues: Efficiently process elements according to their priority.
  • Heap Sort: A sorting algorithm that uses a Heap to arrange elements.
  • Task Scheduling: Process tasks based on their priority.
  • Graph Algorithms: Used in algorithms such as Dijkstra’s shortest path algorithm.

A Heap is a tree-based data structure that maintains a specific relationship between parents and children.

We learned:

  • Min Heap keeps the smallest element at the root.
  • Max Heap keeps the largest element at the root.
  • A Binary Heap can be represented using an array.
  • Insertion uses Heapify Up.
  • Deletion uses Heapify Down.

Heaps are especially useful when we frequently need to access and remove the smallest or largest element.

In the next article, we’ll explore Recursion: Understanding the Basics, where we’ll learn how a function can call itself to solve a problem.


Further reading: GeeksforGeeks – Binary Heap · University of Illinois – Heaps and Priority Queues

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DSA · Part 15

Stack Data Structure: Understanding LIFO

Learn how the Stack data structure works using the LIFO principle, with simple examples, basic operations, C implementation, and real-world applications.

3 min read
DSA · Part 11

Linear Search vs. Binary Search

Learn how Linear Search and Binary Search work, compare their efficiency, and understand when to use each method with simple examples and…

4 min read
DSA · Part 20

Recursion: Understanding the Basics

Understand recursion, base cases, recursive calls, and the call stack. Learn how to trace recursive functions and calculate factorial using simple C…

5 min read

Ask Farhan

Ask anything about Farhan