Heap is a data structure which is constructed based on the complete binary tree. A complete binary tree is a tree with all the nodes except leaf nodes are completely filled and all the nodes are left aligned.
There are two types of heaps:
1)Max-Heap
2)Min-Heap
1)Max-Heap:
Max heap is a data structure where the node has a value greater than all of its children.
2)Min-Heap
Min heap is a data structure where the node has a minimum value compare to all of its children.
In C++ STL there is a priority queue in the container which is the implementation of heap. It provides APIs for the heap data structure. Following are the APIs provided by C++ STL priority_queue:
empty():
This function returns true if the priority queue is empty and false if the queue is not empty.
Ex: priority_queue<int> pq;
pq.empty();
size():
This function returns the size of the priority queue. Here size means number of elements the priority queue is holding. If it is holding 10 elements it returns 10.
Ex: priority_queue<int> pq;
int sz = pq.size();
top():
This function returns the top element of the priority queue. If it a max heap then top returns the maximum element in the priority queue. If it is a min heap it returns the minimum element in the priority queue.
Ex: priority_queue<int> pq;
auto val = pq.top();
push():
This function pushes the element into the queue. It rearranges the tree internally by itself if the re arrangement is required.
Ex: priority_queue<int> pq;
pq.push(10);
pop():
This function removes the top element from the priority queue. If it is a max heap then basically it removes the maximum element from the queue. If it is a min heap, then it removes the minimum element from the priority queue.
Ex: priority_queue<int> pq;
pq.pop();
swap():
This function swaps the elements from one heap with the other heap.
Ex: priority_queue<int> pq1;
priority_queue<int> pq2;
pq1.swap(pq2);
emplace():
This function inserts the element into the priority queue. Main difference between push() and emplace() is:
In push we have to provide the object as a parameter in order to push but in emplace we can pass value where it creates the object internally and inserts. The importance of emplace() is not possible to observe on primitive data types but when it comes to user defined data types it makes lot of sense.
Ex: priority_queue <pq>;
pq.emplace(10);
value_type():
It acts as a synonym for the type of element that is being stored in the priority queue. If the priority queue is storing int, then the value_type will return int.
Ex: priority_queue<int>::value_type another_int;
priority_queue<int> pq;
another_int = 5;
pq.insert(another_int);
By default priority_queue<int> creates max heap. In order to create min heap some extra parameters has to passed to the priority queue. Syntax for creating min heap is:
priority_queue<int, vector<int>, greater<int>>
Here one interesting observation is that for creating max heap just declare it as priority_queue<int> because second and third parameters are default which are vector<> and less<> which makes it max heap by default. So, in order to create min heap we have to pass third parameter as greater<>. That's why we have to create it as: priority_queue<int, vector<int>, greater<int>>
Example code using priority queue:
Output of the above code: 50 40 30 20 10
Example using custom compare function in priority queues:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct dist{
int height;
string name;
dist(int h, string n):height(h), name(n){}
};
bool operator<(dist const& a, dist const& b){
return a.height < b.height;
}
int main()
{
priority_queue<dist, vector<dist>> pq;
dist d1(170, "sreenivas");
dist d2(190, "guru");
dist d3(172, "prathyush");
pq.push(d1);
pq.push(d2);
pq.push(d3);
while(!pq.empty()){
dist d = pq.top();
cout<<d.name<<endl;
pq.pop();
}
return 0;
}Output:
guru
prathyush
sreenivas
Comments
Post a Comment