Signup/Sign In

C++ Implementing Min Heap using Priority Queue Program

Hello Everyone!

In this tutorial, we will learn about the Concept of Min Heap and implementing it using a Priority Queue, in the C++ programming language.

Min Heap Data Structure:

Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled. In Min Heap, both the children of each of the nodes are greater than their parents.

To understand the basic functionality of the Priority Queue in CPP, we will recommend you to visit the C++ STL Priority Queue, where we have explained this concept in detail from scratch.

For a better understanding of its implementation, refer to the well-commented C++ code given below.

Code:

#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()
{
    cout << "\n\nWelcome to Studytonight :-)\n\n\n";
    cout << " =====  Program to demonstrate the Implementation of Min Heap using a Priority Queue, in CPP  ===== \n\n";

    int i;

    /* Declaring a Priority Queue of integers
    Note: by default the priority queue is Max heap in c++ : priority_queue<int> q
    To create a Min heap, follow the below declaration of the Priority Queue
    */
    priority_queue<int, vector<int>, greater<int>> minHeap;

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

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

    cout << "\n\nThe first element or the element with the highest priority is: " << minHeap.top();
    ;

    cout << "\n\nThe elements of the Min Heap are: ";
    show(minHeap);

    cout << "\n\nAfter Deleting the first or the smallest element from the Min Heap, it becomes: ";
    minHeap.pop();
    show(minHeap);

    cout << "\n\nThe number of elements in the Min Heap after deleting the smallest element are : " << minHeap.size();
    ;

    cout << "\n\n\n";

    return 0;
}

Output:

C++ Min Heap

We hope that this post helped you develop a better understanding of the concept of Min Heap and its implementation using a Priority Queue in C++. For any query, feel free to reach out to us via the comments section down below.

Keep Learning : )



About the author:
Nikita Pandey is a talented author and expert in programming languages such as C, C++, and Java. Her writing is informative, engaging, and offers practical insights and tips for programmers at all levels.