Implementing a MaxHeap in C++

Introduction

In my first article, I want to explore a Computer Science topic: the heap data structure.

These kinds of theoretical topics are pretty common in technical interviews, and although I have never used them in my day-to-day job, the applications of these data structures are exciting and worth studying to improve your problem-solving skills.

In this article, I will explain what a heap is, its uses and how to implement it in C++.

What is a heap?

A heap is a tree data structure that satisfies 2 properties:

• It is a complete binary tree

• The value of a node is greater (max heap) or smaller (min-heap) than or equal to the value of its children

An example of a max heap would be the following:

The example above is both:

• A complete binary tree:

  • All levels are filled except possibly the last level.

  • The last level has all keys as left as possible.

• A max heap:

  • The value of a node is greater than or equal to the value of its children.

Uses of a heap

A useful property of the heap is that the root node is always the tree's maximum (max heap) or minimum (min-heap) value.

This property becomes handy to implement a priority queue, where the root node is always the next element to be processed.

Priority queues are useful in many applications, for example:

• A CPU scheduler, where the tasks with the highest priority are processed first.
• A web server, where the requests with the highest priority are processed first.

Another use of the heap is to implement a sorting algorithm. The idea is to insert all the elements in the heap and then extract them individually. The result will be a sorted ascending list (min-heap) or descending list (max heap).

Heap Representation

The most common way to represent a heap is through an array.

Thanks to the properties of a complete binary tree, the root node is the first element of the array, and its children are the second and third elements. Then, the children of the second element are the fourth and fifth elements, and so on.

We get the children of a node with the following formulas, assuming that the array is 0-indexed:

$$left(i) = (2 * i) + 1$$

$$right(i) = (2 * i) + 2$$

To get the parent of a node we use the following formula:

$$parent(i) = FLOOR(\frac{i-1}{2})$$

Implementation

We will assume a max heap implementation in this article. Let's imagine we are constructing a priority queue for an application that processes tasks. Each task has a priority and we want to process the tasks with the highest priority first.

This will be our Heap class structure:

// MaxHeap.h
#inclde <string>
#include <vector>
#include <cmath>

struct Task {
    int priority;
    std::string id;
};

class MaxHeap {
  public:
    MaxHeap(){
        heap = std::vector<Task>();
    }
    ~MaxHeap();
    void insert(Task task);
    bool isEmpty();
    Task extractMax();
    static int getLeft(int i);
    static int getRight(int i);
    static int getParent(int i);
  private:
    std::vector<Task> heap;
    void swap(int i, int j);
    unsigned int highestIndex(unsigned int i);
    void heapify(unsigned int i);
}

In the above code, we have a Task struct containing the task's priority and id.

The MinHeap class consists of the following:

• 3 public methods that allow other classes to insert a task, extract the task with the highest priority and check if the heap is empty.

• 3 static methods, that allow to get the children and parent of a node.

  • These methods are static because they don't need to access any state of the Heap class, they just need the index of the node.

• A private vector of tasks will be used to store the tasks in the heap.

  • This vector is initialized in the constructor of the class.

• 3 private methods, that the public methods will use to insert and extract tasks from the heap.

We also import the vector, string and cmath libraries. The vector library will be used to store the tasks in the heap, the string library to store the ID of the task and the cmath library to use the floor function.

Let's start the implementation of static methods to get the children and parent of a node, this will be pretty straightforward, as we just need to apply the formulas that we saw before:

// MaxHeap.cpp
#include "MaxHeap.h"

int MaxHeap::getLeft(int i) {
    return (2 * i) + 1;
}

int MaxHeap::getRight(int i) {
    return (2 * i) + 2;
}

int MaxHeap::getParent(int i) {
    return floor((i - 1) / 2);
}

Now, let's take a look at the private functions that will be used for the insertion and extraction of the tasks:

// MaxHeap.cpp

void MaxHeap::swap(int i, int j) {
    Task temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

unsigned int MaxHeap::highestIndex(unsigned int i) {
    unsigned int highest = i;
    unsigned int left = MinHeap::getLeft(i);

    // No left child, hence no right child, return parent
    if (left >= heap.size()) {
        return highest;
    }

    if (heap[left].priority > heap[highest].priority) {
        highest = left;
    }

    unsigned int right = MinHeap::getRight(i);

    if (right < heap.size() && heap[right].priority > heap[highest].priority) {
        highest = right;
    }

    return highest;
}

void MaxHeap::heapify(unsigned int i) {
    unsigned int highest = highestIndex(i);
    if (highest != i) {
        swap(i, highest);
        heapify(highest);
    }
}

Let's go through the code above:

The swap function swaps the position of two elements in the heap, given their indexes.

The highestIndex function returns the index of the highest priority element between the node with index i and its children. If the node with index i has no children, it returns the index of the node with index i.

Finally, the heapify function takes a node with an index i and swaps it with its highest-priority child if the child has a higher priority than the node. It then calls itself recursively with the index of the child, this will ensure that the heap property is satisfied from the node with index i all the way to the leaf nodes.

Believe it or not, that's as complicated as it gets. Now that we have the static methods and the private methods, we can implement the public methods that will be used to insert and extract tasks from the heap.

// MaxHeap.cpp

void MaxHeap::insert(Task task){
  unsigned int pos = heap.size();
  heap.push_back(task);
  while (pos > 0 && heap[MaxHeap::getParent(pos)].priority < heap[pos].priority) {
    swap(pos, MaxHeap::getParent(pos));
    pos = MaxHeap::getParent(pos);
  }
}

bool MaxHeap::isEmpty() {
  return heap.size() == 0;
}

Task MaxHeap::extractMax() {
  if (isEmpty()) {
    throw "Heap is empty";
  }
  Task max{ heap[0].priority, heap[0].id };
  heap.erase(heap.begin());

  if (isEmpty()) return max; 

  heapify(0);
  return max;
}

The insert method takes a task and inserts it in the heap. It first inserts the task at the end of the heap and then swaps it with its parent until the heap property is satisfied.

The isEmpty method returns true if the heap is empty, and false otherwise.

The extractMax method returns the task with the highest priority and removes it from the heap. It first checks if the heap is empty, and if it is, it throws an exception. Then it stores the task with the highest priority in a variable, removes it from the heap and calls the heapify method with the root node.

Now that we have implemented the heap, we can use it in our application:

// main.cpp

#include <iostream>
#include "MaxHeap.h"

int main() {
    MaxHeap heap = MaxHeap();
    heap.insert(Task{ 1, "Task 1" });
    heap.insert(Task{ 2, "Task 2" });
    heap.insert(Task{ 3, "Task 3" });

    while (!heap.isEmpty()) {
        Task task = heap.extractMax();
        std::cout << "Task with id " << task.id << " and priority " << task.priority << " extracted" << std::endl;
    }

    // Output:
    // Task with id Task 3 and priority 3 extracted
    // Task with id Task 2 and priority 2 extracted
    // Task with id Task 1 and priority 1 extracted

    return 0;
}

Conclusion

In this article, we have seen what a heap is, its uses and how to implement a max heap in C++.

As I stated, these topics allow you to improve your problem-solving skills. It allows you to think about simple solutions to complex problems, and it is a good way to practice your programming skills.

I hope you enjoyed this article, and if you have any questions or suggestions, please let me know in the comments below.