C++ Program to Implement a Heap

Table of Contents

Introduction

Heaps are an essential data structure in computer science, widely used for various applications such as priority queues, heap sort, and graph algorithms like Dijkstra’s shortest path. In a heap, every parent node is either greater than or equal to (Max-Heap) or less than or equal to (Min-Heap) its child nodes. In this article we will learn to write a C++ Program to Implement a Heap of both Min-Heap and Max-Heap.

Prerequisites

Before diving into the implementation, it’s important to have a basic understanding of:

Data Structures: Specifically, trees and arrays.
C++ Programming: Knowledge of classes, vectors, and basic syntax.
Algorithms: Familiarity with basic algorithms and their complexity.

Heap Structure

Min-Heap and Max-Heap Properties

Min-Heap Property: For any given node i, the key of i is less than or equal to the keys of its children.
Max-Heap Property: For any given node i, the key of i is greater than or equal to the keys of its children.

Formula for Parent and Child Nodes

Parent of node $i$ :

$\text{Parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor$

Left child of node $i$ :

$\text{Left}(i) = 2i + 1$

Right child of node $i$ :

$\text{Right}(i) = 2i + 2$

1. Implementing Min-Heap

1.1 Min-Heap Class Definition

The Min-Heap ensures that the smallest element is always at the root.

#include <iostream>
#include <vector>
#include <climits>

class MinHeap {
    std::vector<int> heap;

    void heapifyUp(int index);
    void heapifyDown(int index);

public:
    void insert(int key);
    int extractMin();
    void display();
};

void MinHeap::heapifyUp(int index) {
    int parent = (index - 1) / 2;
    if (index && heap[parent] > heap[index]) {
        std::swap(heap[index], heap[parent]);
        heapifyUp(parent);
    }
}

void MinHeap::heapifyDown(int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;

    if (left < heap.size() && heap[left] < heap[smallest])
        smallest = left;
    if (right < heap.size() && heap[right] < heap[smallest])
        smallest = right;
    if (smallest != index) {
        std::swap(heap[index], heap[smallest]);
        heapifyDown(smallest);
    }
}

void MinHeap::insert(int key) {
    heap.push_back(key);
    heapifyUp(heap.size() - 1);
}

int MinHeap::extractMin() {
    if (heap.size() == 0)
        return INT_MAX;
    int root = heap.front();
    heap[0] = heap.back();
    heap.pop_back();
    heapifyDown(0);
    return root;
}

void MinHeap::display() {
    for (int i : heap)
        std::cout << i << " ";
    std::cout << std::endl;
}

1.2 Example Usage of Min-Heap

int main() {
    MinHeap minHeap;
    minHeap.insert(3);
    minHeap.insert(1);
    minHeap.insert(6);
    minHeap.insert(5);
    minHeap.insert(2);
    minHeap.insert(4);

    std::cout << "Min-Heap: ";
    minHeap.display();

    std::cout << "Extract Min: " << minHeap.extractMin() << std::endl;
    std::cout << "Min-Heap after extraction: ";
    minHeap.display();

    return 0;
}

1.3 Output for Min-Heap Example

Min-Heap: 1 2 4 5 3 6 
Extract Min: 1
Min-Heap after extraction: 2 3 4 5 6

2. Implementing Max-Heap

2.1 Max-Heap Class Definition

The Max-Heap ensures that the largest element is always at the root.

#include <iostream>
#include <vector>
#include <climits>

class MaxHeap {
    std::vector<int> heap;

    void heapifyUp(int index);
    void heapifyDown(int index);

public:
    void insert(int key);
    int extractMax();
    void display();
};

void MaxHeap::heapifyUp(int index) {
    int parent = (index - 1) / 2;
    if (index && heap[parent] < heap[index]) {
        std::swap(heap[index], heap[parent]);
        heapifyUp(parent);
    }
}

void MaxHeap::heapifyDown(int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;

    if (left < heap.size() && heap[left] > heap[largest])
        largest = left;
    if (right < heap.size() && heap[right] > heap[largest])
        largest = right;
    if (largest != index) {
        std::swap(heap[index], heap[largest]);
        heapifyDown(largest);
    }
}

void MaxHeap::insert(int key) {
    heap.push_back(key);
    heapifyUp(heap.size() - 1);
}

int MaxHeap::extractMax() {
    if (heap.size() == 0)
        return INT_MAX;
    int root = heap.front();
    heap[0] = heap.back();
    heap.pop_back();
    heapifyDown(0);
    return root;
}

void MaxHeap::display() {
    for (int i : heap)
        std::cout << i << " ";
    std::cout << std::endl;
}

2.2 Example Usage of Max-Heap

int main() {
    MaxHeap maxHeap;
    maxHeap.insert(3);
    maxHeap.insert(1);
    maxHeap.insert(6);
    maxHeap.insert(5);
    maxHeap.insert(2);
    maxHeap.insert(4);

    std::cout << "Max-Heap: ";
    maxHeap.display();

    std::cout << "Extract Max: " << maxHeap.extractMax() << std::endl;
    std::cout << "Max-Heap after extraction: ";
    maxHeap.display();

    return 0;
}

2.3 Output for Max-Heap Example

Max-Heap: 6 5 4 1 2 3 
Extract Max: 6
Max-Heap after extraction: 5 3 4 1 2

Conclusion

Heaps are powerful data structures that facilitate efficient data management and algorithm optimization. In this article, we have explored the implementation of both Min-Heap and Max-Heap in C++.