Pin-Jiun
commented
1 year ago priority_queue with tuple
首先先使用struct建立priority_queue
#include <queue>
using namespace std;
struct S
{
int m_n1;
int m_n2;
int m_n3;
S(int n1, int n2, int n3) : m_n1(n1), m_n2(n2), m_n3(n3)
{
}
bool operator<(const struct S& other) const
{
//Your priority logic goes here
return m_n1 < other.m_n1;
}
};
int main()
{
priority_queue<S> pq;
//Add the elements to the queue
pq.push(S(1,2,3));
pq.push(S(4,2,3));
pq.push(S(2,2,3));
//This element will be S(4,2,3)
S s1 = pq.top();
pq.pop();
return 0;
}#include <tuple>
#include <iostream>
#include <queue>
using namespace std;
void print(priority_queue<tuple<int,
int, char> > priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a tuple itself
tuple<int, int, char> Tuple =
priorityQueue.top();
cout << "[ ";
cout << get<0>(Tuple) << ' ' <<
get<1>(Tuple) << ' ' <<
get<2>(Tuple);
cout << ']';
cout << '\n';
// Pop out the topmost tuple
priorityQueue.pop();
}
}
int main()
{
// Declaring a priority queue of tuple
priority_queue<tuple<int, int, char> > priorityQueue;
// Declaring a tuple
tuple<int, int, char> tuple1;
// Initializing the tuple
tuple1 = make_tuple(5, 1, 'G');
// Pushing the tuple in the priority queue
priorityQueue.push(tuple1);
// Declaring another tuple
tuple<int, int, char> tuple2(2, 5, 'e');
priorityQueue.push(tuple2);
// Declaring another tuple
tuple<int, int, char> tuple3(4, 3, 'k');
priorityQueue.push(tuple3);
print(priorityQueue);
return 0;
}output
[ 5 1 G]
[ 4 3 k]
[ 2 5 e]working of customized priority queue of tuples
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Comparator
// we can use class also but then
// we will need to make the function
// public as class is by default private
struct myComparator
{
int operator()(const tuple<int, int,
string>& tuple1,
const tuple<int, int,
string>& tuple2)
{
// Second element of tuples is equal
if (get<1>(tuple1) == get<1>(tuple2))
{
// first element of tuples is equal
if (get<0>(tuple1) == get<0>(tuple2))
{
if (get<2>(tuple1) <= get<2>(tuple2))
return true;
return false;
}
return get<0>(tuple1) <= get<0>(tuple2);
}
return get<1>(tuple1) <= get<1>(tuple2);
}
};
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority
// queue
void print(priority_queue<tuple<int, int,
string>,
vector<tuple<int, int, string> >,
myComparator> priorityQueue)
{
while (!priorityQueue.empty())
{
// Each element of the priority
// queue is a tuple itself
tuple<int, int, string> Tuple =
priorityQueue.top();
cout << "[ ";
cout << get<0>(Tuple) << ' ' <<
get<1>(Tuple) << ' ' <<
get<2>(Tuple);
cout << ']';
cout << '\n';
// Pop out the topmost tuple
priorityQueue.pop();
}
}
// Driver code
int main()
{
// Declaring a priority queue of
// tuples by passing a custom comparator
priority_queue<tuple<int, int, string>,
vector<tuple<int, int, string> >,
myComparator>
priorityQueue;
// Declaring a tuple
tuple<int, int, string> tuple1;
// Initializing the tuple
tuple1 = make_tuple(0, 0,
"Geeks");
// Pushing the tuple in the
// priority queue
priorityQueue.push(tuple1);
// Declaring a tuple
tuple<int, int, string> tuple2;
// Initializing the tuple
tuple2 = make_tuple(0, 1,
"Programming");
// Pushing the tuple in the
// priority queue
priorityQueue.push(tuple2);
// Declaring a tuple
tuple<int, int, string> tuple3;
// Initializing the tuple
tuple3 = make_tuple(1, 2,
"Geeks");
// Pushing the tuple in the
// priority queue
priorityQueue.push(tuple3);
// Declaring a tuple
tuple<int, int, string> tuple4;
// Initializing the tuple
tuple4 = make_tuple(1, 3,
"Programming");
// Pushing the tuple in the
// priority queue
priorityQueue.push(tuple4);
// Calling print function
print(priorityQueue);
return 0;
}
priority_queue
歸類在queue, 只需要
#include <queue>就好宣告
priority_queue預設使用vector轉換成priority_queue
priority_queue <int> pq預設為max heap(最大的優先取出)=priority_queue<int,vector<int>,less<int> >若要改成最小的優先取出，需要在宣告時就告知是最小的優先取出，使用函式物件(function object)的
greater<int>priority_queue<T, vector<T>, greater<T> > pq; 改成由小排到大常見method(沒有
front()back())empty()size()push()pop()priority_queue.top()Returns a constant reference to the top element in the priority_queue.priority_queue.pop()Removes the element on top of the priority_queue, effectively reducing its size by one.範例1 會使用第一個數字當作key進行排列
output1
範例2
output2
參考資料 https://yuihuang.com/cpp-stl-priority-queue/ https://ithelp.ithome.com.tw/articles/10269601 https://www.geeksforgeeks.org/priority-queue-of-pairs-in-c-ordered-by-first/