In this article at OpenGenus, we are going to study and explore Min / Max Heap in C++ using STL. We will see their definition, usage and how we are going to apply them to solve various complex problems in C++ language.

TABLE OF CONTENTS

1. INTRODUCTION
2. MIN HEAP
3. PRIORTY QUEUE
4. IMPLEMETATION OF MIN HEAP USING C++ STL
5. MAX HEAP
6. IMPLEMENTATION OF MAX HEAP USING C++ STL
7. EXAMPLE
8. TIME AND SPACE COMPLEXITY.

INTRODUCTION

In a Heap, a unique type of tree-based data structure, the tree is a complete binary tree.

Types of heap data structure

Generally, Heaps can be of two types:

Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

MIN HEAP

A min heap is a specialized data structure that represents a complete binary tree where the value of each node is smaller than or equal to the values of its children. In other words, in a min heap, the parent nodes always have smaller values compared to their child nodes.

The key property of a min heap is that the minimum element in the heap is always stored at the root node. This allows for efficient retrieval of the minimum element in constant time, regardless of the size of the heap.

Min heaps are primarily used to efficiently solve problems that involve finding the minimum or maintaining a priority queue, where the minimum element needs to be accessed quickly. They have applications in various algorithms, such as Dijkstra's algorithm for finding the shortest path in a graph and the heap sort algorithm for sorting elements in ascending order.

Operations commonly performed on a min heap include insertion of a new element, extraction of the minimum element, and decreasing the value of an existing element (often used to update priorities in a priority queue). These operations maintain the min heap property, ensuring that the minimum element is always at the root.

PRIORTY QUEUE

We can implement a min heap using c++ STL with help of a data structure called "PRIORTY QUEUE".

A C++ priority queue is a type of container adapter, specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue, and elements are in non-increasing or non-decreasing order (hence we can see that each element of the queue has a priority {fixed order}).

SYNTAX :

priority_queue<int> prq;

In C++ STL, the top element is always the greatest by default. We can also change it to the smallest element at the top. Priority queues are built on the top of the max heap and use an array or vector as an internal structure. In simple terms, STL Priority Queue is the implementation of Heap Data Structure.

Some of the functions of the priorty queue along with their use are :

1. push() and pop() : The push() method is used to insert an element into the priority queue. To remove an element from the priority queue the pop() method is used because this removes the element with the highest priority by defualt.
2. top() : The top element of the Priority Queue could be accessed using the top() method.
3. empty() : We use the empty() method to check if the priority_queue is empty. This method returns a boolean value as :
   True – It is returned when the priority queue is empty and is represented by 1.
   False – It is produced when the priority queue is not empty or False and is characterized by 0.
4. size() : It determines the size of a priority queue. In simple terms, the size() method is used to get the number of elements present in the Priority Queue.

IMPLEMENTATION OF MIN HEAP USING C++ STL

Now for implementation of min heap we are going to use a priorty queue. Following syntax has to be used for creating a priorty queue.

SYNTAX :

priority_queue <int, vector<int>, greater<int>> minHeap;

Code :

#include<bits/stdc++.h>
using namespace std;

int main()
{
	
	// Create a priority queue with a custom comparator to make it a min heap
	priority_queue<int, vector<int>, greater<int>> minHeap;

	// Insert elements from the vector into the min heap
	minHeap.push(5);
	minHeap.push(2);
	minHeap.push(9);
	minHeap.push(1);
	minHeap.push(7);

	// Extract and print the minimum elements from the min heap
	while (!minHeap.empty()) {
		int minElement = minHeap.top();
		minHeap.pop();
		cout << minElement << " ";
	}

}

In this example, we first develop a custom comparator called greater and a standard priority queue called minHeap. It functions as a min heap since this comparator makes sure that the elements are stored in ascending order.

The push() function is then used to add the elements to the minHeap. The min heap property is automatically maintained by the push() operation.

Finally, we use the top() function to fetch the minimum element from the minHeap and the pop() function to remove it from the heap. Using a while loop, we output the minimum elements in ascending order until the heap is empty.

OUTPUT

1 2 5 7 9

MAX HEAP

A max heap is a specialized data structure that represents a complete binary tree where the value of each node is greater than or equal to the values of its children. In other words, in a max heap, the parent nodes always have larger values compared to their child nodes.

The key property of a max heap is that the maximum element in the heap is always stored at the root node. This allows for efficient retrieval of the maximum element in constant time, regardless of the size of the heap.

Operations commonly performed on a max heap include insertion of a new element, extraction of the maximum element, and increasing the value of an existing element (often used to update priorities in a priority queue). These operations maintain the max heap property, ensuring that the maximum element is always at the root.

IMPLEMENTATION OF MAX HEAP USING C++ STL

By defualt the priorty queue works as a max heap.

Code

#include<bits/stdc++.h>
using namespace std;

int main() {
	// Create a priority queue (max heap) of integers
	priority_queue<int> maxHeap;

	// Insert elements into the max heap
	maxHeap.push(5);
	maxHeap.push(2);
	maxHeap.push(9);
	maxHeap.push(1);
	maxHeap.push(7);

	// Extract and print the maximum elements from the max heap
	while (!maxHeap.empty()) {
		int maxElement = maxHeap.top();
		maxHeap.pop();
		cout << maxElement << " ";
	}

}

In this example, we create a priority_queue named maxHeap without specifying any comparator. By default, it creates a max heap. We then insert elements into the maxHeap using the push() function, and the heap automatically maintains the max heap property.

Finally, we extract the maximum elements from the maxHeap using the top() function to retrieve the maximum element and the pop() function to remove it from the heap. The maximum elements are printed in descending order because it is a max heap.

OUTPUT

9 7 5 2 1

EXAMPLE

#include<bits/stdc++.h>
using namespace std;

class Task {
public:
	string name;
	int priority;

	Task(const string& name, int priority)
	{
		this->name = name;
		this->priority = priority;
	}

	// Overloading comparison operators
	bool operator<(const Task& other) const {
		return priority < other.priority;
	}

	bool operator>(const Task& other) const {
		return priority > other.priority;
	}
};

int main() {
	// Create a priority queue of Task objects
	priority_queue<Task, vector<Task>, less<Task>> taskQueue;

	// Adding tasks to the priority queue
	taskQueue.push(Task("Ram", 3));
	taskQueue.push(Task("Rajiv", 1));
	taskQueue.push(Task("Raju", 2));

	// Accessing the tasks in priority order
	while (!taskQueue.empty()) {
		Task task = taskQueue.top();
		cout << "Task Name: " << task.name << ", Priority: " << task.priority <<endl;
		taskQueue.pop();
	}

	return 0;
}

In this example, we define the Task class with name and priority data members. We then overload the < and > operators for the Task class to define how the priority queue should compare the objects.

The priority_queue is used to create the priority queue of Task objects. The default comparison function for the priority queue is less, which sorts elements in ascending order. If We want to sort elements in descending order, we can use greater instead.

OUTPUT

Task Name: Ram, Priority: 3
Task Name: Raju, Priority: 2
Task Name: Rajiv, Priority: 1

As you can see, the tasks are dequeued from the priority queue based on their priority value.

TIME AND SPACE COMPLEXITY

For both min heap and max heap:
Insertion, deletion : O(log N) where n = number of elements
Searching : O(N)

Space complexity for creating a heap is O(N).