Implementing Min Heap Using Priority Queue

Introduction

In this lab, we will learn how to implement a Min Heap using a Priority Queue in C++. We will implement a C++ program that can perform basic operations on a Min Heap.

Create a new C++ program

Create a new C++ program in the ~/project directory by running the following commands in the terminal:

cd ~/project
touch main.cpp

Include the necessary header files

We will start by including the necessary header files in our program:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

Define the show() function

Next, we define a function that will print the elements of the Min Heap. This function takes a priority queue as an argument and uses a copy of the priority queue to maintain the original priority queue.

// Function to print the elements of the Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copying the Priority Queue into another to maintain the original Priority Queue
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Printing the top most element
        mh.pop();                 // Deleting the top most element to move to the next
    }

    cout << endl;
}

Implement the main() function

In the main() function, we will create a Priority Queue of integers and fill it with elements.

int main()
{
    // Creating a Priority Queue of integers
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Filling the elements into the Priority Queue
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Printing the number of elements in the Min Heap
    cout << "The number of elements in the Min Heap are : " << minHeap.size() << endl;

    // Printing the first element or the element with the highest priority
    cout << "The first element or the element with the highest priority is: " << minHeap.top() << endl;

    // Printing the elements of the Min Heap
    cout << "The elements of the Min Heap are: ";
    show(minHeap);

    // Deleting the first or the smallest element from the Min Heap
    minHeap.pop();

    // Printing the Min Heap after deleting the smallest element
    cout << "After Deleting the first or the smallest element from the Min Heap, it becomes: ";
    show(minHeap);

    // Printing the number of elements in the Min Heap after deleting the smallest element
    cout << "The number of elements in the Min Heap after deleting the smallest element are : " << minHeap.size() << endl;

    return 0;
}

Compile and run the program

To compile the program, run the following command in the terminal:

g++ main.cpp -o main

This command compiles the main.cpp source code and creates an executable named main.

To run the program, execute the following command:

./main

Full code of main.cpp

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Function to print the elements of the Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copying the Priority Queue into another to maintain the original Priority Queue
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Printing the top most element
        mh.pop();                 // Deleting the top most element to move to the next
    }

    cout << endl;
}

int main()
{
    // Creating a Priority Queue of integers
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Filling the elements into the Priority Queue
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Printing the number of elements in the Min Heap
    cout << "The number of elements in the Min Heap are : " << minHeap.size() << endl;

    // Printing the first element or the element with the highest priority
    cout << "The first element or the element with the highest priority is: " << minHeap.top() << endl;

    // Printing the elements of the Min Heap
    cout << "The elements of the Min Heap are: ";
    show(minHeap);

    // Deleting the first or the smallest element from the Min Heap
    minHeap.pop();

    // Printing the Min Heap after deleting the smallest element
    cout << "After Deleting the first or the smallest element from the Min Heap, it becomes: ";
    show(minHeap);

    // Printing the number of elements in the Min Heap after deleting the smallest element
    cout << "The number of elements in the Min Heap after deleting the smallest element are : " << minHeap.size() << endl;

    return 0;
}

Summary

In this lab, we learned how to implement a Min Heap using a Priority Queue in C++. We defined a function to print the elements of the Min Heap, created a Priority Queue of integers, filled it with elements, and printed the number of elements in the Min Heap, the first element or the element with the highest priority, the elements of the Min Heap, the Min Heap after deleting the smallest element, and the number of elements in the Min Heap after deleting the smallest element.