Hello guys , This time I am gonna tell you about priority_queue.
Priortiy_queue is a container adaptor,meaning that it is implemented on top of some underlying container type. By default that container
is Vector but a different type can be used too.
Before moving on i would like you to tell what is a Max_Heap:
please go to this link if you know nothing like JOHN SNOW about HEAP
priority_queue is just like a normal queue except the element removed from the queue is always the greatest among the all the elements of the queue , thus this
container is usually used to replicate Max Heap in C++ . Elements in Priority_queue can be inserted or removed in a time complexity of O(log(n)).
functions used :
1. empty()
2. size()
3. top()
4.push_back()
5. pop_back()
6. make_heap()
7. push_heap()
8. pop_heap()
9. reverse()
10.swap(x,y) -> exchanges the content of X and Y . X and Y are the priority_queue containers of the same type. Their size may be different
11.compare -> used to determine whether one element is greater than the other element or not.
if Compare(x,y) is true , then x is smaller than y
We can use any kind of container to store a priority_queue like , map , queue , dequeue etc
We can reverse the priorities also
example :
Here we are making a Heap without using a priority_queue
//make_heap,push_heap,pop_heap,reverse: -> all are included from #include<algorithm> */
#include<iostream>
#include<algorithm>
#include<queue>
#include <vector>
using namespace std;
int main()
{
int myints[] ={10,20,30,5,15};
vector<int>v(myints,myints+5);
make_heap(v.begin(),v.end());
cout<<"initial max heap: "<<v.front()<<endl;
pop_heap(v.begin(),v.end());
v.pop_back(); // pops the last elemnt from the vector
v.push_back(99);
push_heap(v.begin(),v.end());
cout<<"max heap after push: "<<v.front();
sort_heap(v.begin(),v.end()); // sorts th element of the heap
cout<<"final sorted range: ";
for(int i =0;i<v.size();i++)
{
cout<<v[i]<<endl;
}
reverse(v.begin(),v.end()); // now the vector is reversed
for(int i =0;i<v.size();i++)
{
cout<<v[i]<<endl;
}
}}
/*The most important property of priority_queue is that it does not allow iterations through its elements */
#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int>pq;
priority_queue<int>zz;
pq.push(10);
pq.push(30);
pq.push(40);
pq.push(90);
pq.push(100);
pq.push(60);
pq.push(10);
zz.push(200);
zz.push(530);
zz.push(420);
zz.push(910);
zz.push(105);
zz.push(160);
zz.push(80);
cout<<pq.size()<<endl;
cout<<pq.top()<<endl;
pq.pop();
cout<<pq.top()<<endl;
pq.pop();
cout<<pq.top()<<endl;
pq.pop();
cout<<pq.top()<<endl;
pq.pop();
cout<<pq.top()<<endl;
pq.pop();
}
/* Use of Swap() in priority_queue: */
#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int>pq;
priority_queue<int>zz;
pq.push(10);
pq.push(30);
pq.push(40);
pq.push(90);
pq.push(100);
pq.push(60);
pq.push(10);
zz.push(200);
zz.push(530);
zz.push(420);
zz.push(910);
zz.push(105);
swap(pq,zz);
cout<<"size of pq: "<<pq.size()<<" size of zz: "<<zz.size()<<endl;
}
/* if we can create heap using make_heap , push_heap and pop_heap then why do we use priority_queue ??
it is because of the restriction of iteration of element in priority_queue
**** Have you ever wondered why pop() returns void instead of value_type ??
*/
/* A priority_queue for user defined objects :->
*** priority_queue can be used in many real life situations also
for example :
*/
#include<iostream>
#include<queue>
#include<vector>
class Toast
{
public :
int bread;
int butter;
Toast(int bread ,int butter)
:bread(bread),butter(butter)
{
}
};
// how will you sort a toast given that toast has a value based upon the amount of butter and bread.
//This is done by creating a structure implementing an operator() and efficiently doing less than comparision
struct ToastCompare
{
bool operator()(const Toast &t1 ,const Toast &t2)const
{
int t1value = t1.bread*1000 + t1.butter;
int t2value = t2.bread*1000 + t2.butter;
return t1value<t2value;
}
};
using namespace std;
int main()
{
Toast toast1(2,200);
Toast toast2(1,300);
Toast toast3(1,10);
Toast toast4(3,1);
priority_queue<Toast,vector<Toast>,ToastCompare>q;
q.push(toast1);
q.push(toast2);
q.push(toast3);
q.push(toast4);
while(!q.empty())
{
Toast t = q.top();
cout<<"bread: "<<t.bread<<" butter: "<<t.butter<<endl;
q.pop();
}
}
