C++中集合的优先队列与示例

优先队列

优先队列是一种容器适配器，其特别设计是使队列中的第一个元素是队列中所有元素中最大的元素，并且元素按非增序排列（因此我们可以看到队列的每个元素都有一个优先级（固定顺序））。

与优先队列一起使用的函数：

empty(): 返回队列是否为空。
size(): 返回队列的大小。
top(): 返回队列中最顶部元素的引用。
pop(): 删除队列中的第一个元素。

集合

集合是一种关联式容器，其中每个元素必须是唯一的，因为该元素的值标识它。元素的值添加到集合后无法修改，尽管可以删除并添加该元素的已修改值。

与集合一起使用的函数：

size(): 返回集合中的元素数。
insert(const x)： 将新元素“x”添加到集合中。

集合的优先队列对于设计复杂的数据结构非常有用。

语法：

priority_queue<set<data_type>> priorityQueue
这将集合存储为最大堆优先队列中的一个元素

下面是集合的最大堆优先队列的实现:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print priority
// queue contents
void print(priority_queue<set<int> > priorityQueue)
{
    while (!priorityQueue.empty()) {
        // Each element of the priority
        // queue is a set itself
        set<int> st = priorityQueue.top();
 
        cout << "[ ";
 
        // Print the set elements
        for (auto element : st)
            cout << element << ' ';
        cout << ']';
        cout << '\n';
 
        // Pop out the topmost set
        priorityQueue.pop();
    }
}
 
// Driver code
int main()
{
    // Declaring a max-heap priority
    // queue
    priority_queue<set<int> > priorityQueue;
 
    // Declaring a set of integers
    set<int> set1;
 
    // Inserting into the set
    set1.insert(10);
    set1.insert(1);
    set1.insert(2);
    set1.insert(5);
 
    // Push the set into priority
    // queue
    priorityQueue.push(set1);
 
    // Declaring another set
    set<int> set2;
 
    // Inserting into the set
    set2.insert(2);
    set2.insert(7);
    set2.insert(12);
    set2.insert(1);
 
    // Push the set into priority queue
    priorityQueue.push(set2);
 
    // Declaring another set
    set<int> set3;
 
    // Inserting into the set
    set3.insert(4);
    set3.insert(7);
    set3.insert(12);
    set3.insert(13);
 
    // Push the set into priority queue
    priorityQueue.push(set3);
 
    // Print the priority queue
    print(priorityQueue);
 
    return 0;
}

输出

[ 4 7 12 13 ]
[ 1 2 7 12 ]
[ 1 2 5 10 ]

默认情况下，优先队列是最大堆，因此对于优先队列中的两个集合，具有更大的第一个元素的集合是顶部元素。如果第一个元素相等，则比较集合的第二个值，依此类推。

语法：

priority_queue<set<data_type>, vector<set<data_type>>, greater<set<data_type>>> priorityQueue
这个将set作为一个元素存储在最小堆priority队列中。

下面是实现set最小堆优先级队列的代码：

// C++程序实现的
// 上述方法
#include <bits/stdc++.h>
using namespace std;
 
// 函数打印出优先
// 队列的内容
void print(priority_queue<set<int>,
                          vector<set<int> >,
                          greater<set<int> > >
               priorityQueue)
{
    while (!priorityQueue.empty()) {
        // 每个优先
        // 队列元素本身就是一个集合
        set<int> st = priorityQueue.top();
 
        cout << "[ ";
 
        // 打印集合元素
        for (auto element : st)
            cout << element << ' ';
 
        cout << ']';
        cout << '\n';
 
        // 弹出最顶部的集合
        priorityQueue.pop();
    }
}
 
//主函数
int main()
{
    // 声明一个最小堆
    // 优先队列
    priority_queue<set<int>,
                   vector<set<int> >,
                   greater<set<int> > >
        priorityQueue;
 
    // 声明一组整数
    set<int> set1;
 
    // 插入至set
    set1.insert(10);
    set1.insert(1);
    set1.insert(2);
    set1.insert(5);
 
    // 将该set推入优先
    // 队列
    priorityQueue.push(set1);
 
    // 声明另一组整数
    set<int> set2;
 
    // 插入至set
    set2.insert(2);
    set2.insert(7);
    set2.insert(12);
    set2.insert(1);
 
    // 将该set推入优先
    // 队列
    priorityQueue.push(set2);
 
    // 声明另一组整数
    set<int> set3;
 
    // 插入至set
    set3.insert(4);
    set3.insert(7);
    set3.insert(12);
    set3.insert(13);
 
    // 将该set推入优先
    // 队列
    priorityQueue.push(set3);
 
    // 打印优先队列
    print(priorityQueue);
 
    return 0;
}