C++中的元组优先队列及其示例

优先队列

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

与优先队列相关的函数：

• empty(): 此函数返回队列是否为空。
• size(): 此函数返回队列的大小。
• top(): 返回队列中最顶部的元素的引用。
• push(x): 此函数将元素‘ x ’添加到队列的末尾。

元组

一个 元组 是一个可以容纳多个元素的对象。元素可以是不同的数据类型。元组的元素按将要访问的顺序作为参数初始化。

与元组相关的函数：

• get(): get()用于访问元组值并修改它们，它接受索引和元组名称作为参数来访问特定的元组元素。
• make_tuple(): make_tuple()用于为元组分配值。传递的值应按照元组中声明的值的顺序进行。

本文重点介绍如何在C++中使用元组的优先队列。元组优先队列在设计复杂数据结构时非常有用。
语法1：元组的最大堆优先队列：
priority_queue<tuple<data_type1, data_type2, data_type3>> priorityQueue;

语法2：元组的最小堆优先队列：
priority_queue<tuple<data_type1, data_type2, data_type3>,
vector<tuple<data_type1, data_type2, data_type3>>,
greater<tuple<data_type1, data_type2, data_type3>>> priorityQueue;

语法3：自定义元组优先队列（使用比较器）：
priority_queue<tuple<data_type1, data_type2, data_type3>,
vector<tuple<data_type1, data_type2, data_type3>>, comparator> priorityQueue;

元组的最大堆优先队列：

默认情况下，优先队列为最大堆。因此，在优先队列中出现一对元组时，比较它们的第一个元素，如果两个元组的第一个元素相等，则比较它们的第二个元素，如果第二个元素也相等，则比较第三个元素。具有较大元素的元组将成为优先队列的顶部元素。

示例1： 下面是实现元组的最大堆优先队列的C++程序。

// C++程序实现
//上述方法
#include
using namespace std;
  
//打印优先级队列
//内容。故意传递它
//按值调用，因为我们不想
//从优先级队列中删除元素
void print(priority_queue > priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    //每个优先级的元素
    //队列本身是一个元组
    tuple Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' << 
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    //弹出最顶层的元组
    priorityQueue.pop();
  }
}
  
//驱动程序
int main()
{
  //声明一种优先的队列
  //元组
  priority_queue > priorityQueue;
  
  //声明一个元组
  tuple tuple1;
  
  //初始化元组
  tuple1 = make_tuple(1, 1, 'G');
  
  //将元组推入
  //优先级队列
  priorityQueue.push(tuple1);
  
  //声明另一个元组
  tuple tuple2;
  
  //初始化元组
  tuple2 = make_tuple(2, 2, 'e');
  
  //将元组推入
  //优先级队列
  priorityQueue.push(tuple2);
  
  //声明另一个元组
  tuple tuple3;
  
  //初始化元组
  tuple3 = make_tuple(3, 3, 'e');
  
  //将元组推入
  //优先级队列
  priorityQueue.push(tuple3);
  
  //声明另一个元组
  tuple tuple4;
  
  //初始化元组
  tuple4 = make_tuple(4, 4, 'k');
  
  //将元组推入
  //优先级队列
  priorityQueue.push(tuple4);
  
  //调用打印函数
  print(priorityQueue);
  
  return 0;
}  

输出

[ 4 4 k]
[ 3 3 e]
[ 2 2 e]
[ 1 1 G]

例2： 以下是演示元组的最大堆优先级队列的工作的C++程序。

// C++程序以实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;
  
// 打印优先队列的功能
// 内容。故意传递它
// 按值调用，因为我们不想
// 从优先队列中删除元素
void print(priority_queue<tuple<int, int, 
           string> > priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // 每个优先队列的元素
    // 本身就是一个元组
    tuple<int, int, string> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' << 
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // 弹出顶部的元组
    priorityQueue.pop();
  }
}
  
// 驱动器代码
int main()
{
  // 声明一个优先队列
  // of tuple
  priority_queue<tuple<int, int, 
  string> > priorityQueue;
  
  // 声明一个元组
  tuple<int, int, string> tuple1;
  
  // 初始化元组
  tuple1 = make_tuple(0, 0, "Geeks");
  
  // 将元组推入
  // 优先队列
  priorityQueue.push(tuple1);
  
  // 声明一个元组
  tuple<int, int, string> tuple2;
  
  // 初始化元组
  tuple2 = make_tuple(0, 0, 
                      "Programming");
  
  // 将元组推入
  // 优先队列
  priorityQueue.push(tuple2);
  
  // 声明一个元组
  tuple<int, int, string> tuple3;
  
  // 初始化元组
  tuple3 = make_tuple(1, 2, 
                      "Geeks");
  
  // 将元组推入
  // 优先队列
  priorityQueue.push(tuple3);
  
  // 声明一个元组
  tuple<int, int, string> tuple4;
  
  // 初始化元组
  tuple4 = make_tuple(1, 3, 
                      "Programming");
  
  // 将元组推入
  // 优先队列
  priorityQueue.push(tuple4);
  
  // 调用打印函数
  print(priorityQueue);
  
  返回0;
}  

输出

[ 1 3 Programming]
[ 1 2 Geeks]
[ 0 0 Programming]
[ 0 0 Geeks]

元组的最小堆优先队列：

在最小堆优先队列中，对于一对元组，先比较它们的第一个元素，如果两个元组的第一个元素相等，则比较它们的第二个元素，如果第二个元素也相等，则比较第三个元素。 元素较小的元组成为优先队列的顶部元素。

示例1： 下面是实现元组最小堆优先队列工作的C++程序。

// C++程序实现上述方法
#include 
using namespace std;

//打印优先级队列内容。
//有意地通过值传递函数，因为我们不希望从优先队列中移除元素
void print(priority_queue,
    vector>,
    greater>> priorityQueue)
{
    while (!priorityQueue.empty())
    {
        // 优先级队列的每个元素本身就是一元组
        tuple Tuple =
            priorityQueue.top();

        cout << "[ ";

        cout << get<0>(Tuple) << ' ' <<
            get<1>(Tuple) << ' ' <<
            get<2>(Tuple);
        cout << ']';
        cout << '\n';

        //弹出最顶端的元组
        priorityQueue.pop();
    }
}

//主函数
int main()
{
    // 声明一个具有最小堆优先级的元组优先级队列
    priority_queue,
        vector>,
        greater>> priorityQueue;

    // 声明一个元组
    tuple tuple1;

    // 初始化元组
    tuple1 = make_tuple(1, 1, 'G');

    // 将元组插入优先队列
    priorityQueue.push(tuple1);

    // 声明另一个元组
    tuple tuple2;

    //初始化元组
    tuple2 = make_tuple(2, 2, 'e');

    //将元组插入优先队列
    priorityQueue.push(tuple2);

    // 声明另一个元组
    tuple tuple3;

    //初始化元组
    tuple3 = make_tuple(3, 3, 'e');

    //将元组插入优先队列
    priorityQueue.push(tuple3);

    // 声明另一个元组
    tuple tuple4;

    //初始化元组
    tuple4 = make_tuple(4, 4, 'k');

    //将元组插入优先队列
    priorityQueue.push(tuple4);

    //调用打印函数
    print(priorityQueue);

    return 0;
}  

输出

[ 1 1 G]
[ 2 2 e]
[ 3 3 e]
[ 4 4 k]

示例2： 以下是实现元组最小堆优先级队列的C++程序的工作原理。

// C ++程序实现上述方法
#include 
using namespace std;

//函数打印优先级队列
//内容。故意传递它
//通过值呼叫，因为我们不想要
//从优先级队列中删除元素
void print(priority_queue,
           vector>,
           greater>>
           priorityQueue)
{
  while (!priorityQueue.empty())
  {
    //优先级的每个元素
    //队列本身是一个元组
    tuple Tuple =
              priorityQueue.top();

    cout << "[ ";

    cout << get<0>(Tuple) << ' ' <<
                get<1>(Tuple) << ' ' <<
                get<2>(Tuple);
    cout << ']';
    cout << '\n';

    //弹出最上面的元组
    priorityQueue.pop();
  }
}

//驱动程序
int main()
{
  //声明一种优先级队列
  //元组
  priority_queue,
  vector>,
  greater>>
              priorityQueue;

  //声明一个元组
  tuple tuple1;

  //初始化元组
  tuple1 = make_tuple(0, 0, "Geeks");

  //将元组推入队列中
  priorityQueue.push(tuple1);

  //声明一个元组
  tuple tuple2;

  //初始化元组
  tuple2 = make_tuple(0, 0,
                      "Programming");

  //将元组推入队列中
  priorityQueue.push(tuple2);

  //声明一个元组
  tuple tuple3;

  //初始化元组
  tuple3 = make_tuple(1, 2,
                      "Geeks");

  //将元组推入队列中
  priorityQueue.push(tuple3);

  //声明一个元组
  tuple tuple4;

  //初始化元组
  tuple4 = make_tuple(1, 3,
                      "Programming");

  //将元组推入队列中
  priorityQueue.push(tuple4);

  //调用print函数
  print(priorityQueue);

  return 0;
}  

输出

[ 0 0 Geeks]
[ 0 0 Programming]
[ 1 2 Geeks]
[ 1 3 Programming]

自定义的元组优先级队列：

进一步处理 如何使用STL实现Min Heap？ 是一个必须先决条件，我们在这里学习如何通过将比较器作为参数传递给优先队列来自定义元组的优先队列。

示例1： 以下是实现定制元组优先级队列的C ++程序。

// C++程序，以实现上述方法
#include <bits/stdc++.h>
using namespace std;
  
//比较器（Comparator）
//我们也可以使用类，但那样就需要将函数
//公共化，因为默认情况下类是私有的
struct myComparator 
{
  int operator()(const tuple<int, int, 
                 string>& tuple1,
                 const tuple<int, int, 
                 string>& tuple2)
  {
    //元组的第二个元素相等
    if (get<1>(tuple1) == get<1>(tuple2)) 
    {
      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);
  }
};
  
//用于打印优先队列内容的函数。
//我们故意按值传递，
//因为我们不想从优先队列中删除元素
void print(priority_queue<tuple<int, int, 
           string>,
           vector<tuple<int, int, 
           string> >,
           myComparator>
           priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    //每个元素都是一个元组
    tuple<int, int, string> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' <<
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    //弹出最上面的元组
    priorityQueue.pop();
  }
}
  
//主函数
int main()
{
  //声明一个优先队列中元素为元组
  priority_queue<tuple<int, int, string>,
  vector<tuple<int, int, string> >,
  myComparator> priorityQueue;
  
  //声明一个元组
  tuple<int, int, string> tuple1;
  
  //初始化元组
  tuple1 = make_tuple(0, 0, 
                      "Geeks");
  
  //向优先队列中压入元组
  priorityQueue.push(tuple1);
  
  //声明一个元组
  tuple<int, int, string> tuple2;
  
  //初始化元组
  tuple2 = make_tuple(0, 1, 
                      "Programming");
  
  //向优先队列中压入元组
  priorityQueue.push(tuple2);
  
  //声明一个元组
  tuple<int, int, string> tuple3;
  
  //初始化元组
  tuple3 = make_tuple(1, 2, 
                      "Geeks");
  
  //向优先队列中压入元组
  priorityQueue.push(tuple3);
  
  //声明一个元组
  tuple<int, int, string> tuple4;
  
  //初始化元组
  tuple4 = make_tuple(1, 3, 
                      "Programming");
  
  //向优先队列中压入元组
  priorityQueue.push(tuple4);
  
  //调用print函数
  print(priorityQueue);
  
  return 0;
}  

输出

[ 0 0 Geeks]
[ 0 1 Programming]
[ 1 2 Geeks]
[ 1 3 Programming]

在上面的程序中，对于一对元组，首先比较元组的第二个元素，如果该值相等，则比较第一个元素，如果两个元组的第一个元素相等，则比较第三个元素。否则，小的元素将成为最上面的元素。

例2： 以下是C++程序，演示元组的自定义优先队列的工作原理。

// C++程序实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;

//比较器
//我们也可以使用类，但是
//我们将需要使函数变为
//公共的，因为类默认为私有
struct myComparator
{
  int operator()(const tuple<int, int,
                  string>& tuple1,
                  const tuple<int, int,
                  string>& tuple2)
  {
    //元组的第二个元素相等
    if (get<1>(tuple1) == get<1>(tuple2))
    {
      //元组的第一个元素相等
      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);
  }
};

//打印优先队列
//内容。刻意传递它
//调用按值传递，因为我们不想
//从优先队列中删除元素
void print(priority_queue<tuple<int, int,
          string>,
          vector<tuple<int, int, string> >,
          myComparator> priorityQueue)
{
  while (!priorityQueue.empty())
  {
    // 优先队列的每个元素
    //本身是一个元组
    tuple<int, int, string> Tuple =
          priorityQueue.top();

    cout << "[ ";

    cout << get<0>(Tuple) << ' ' <<
                get<1>(Tuple) << ' ' <<
                get<2>(Tuple);
    cout << ']';
    cout << '\n';

    // 弹出顶部元组
    priorityQueue.pop();
  }
}

//驱动程序
int main()
{
  // 通过传递自定义比较器声明元组的优先队列
  priority_queue<tuple<int, int, string>,
  vector<tuple<int, int, string> >,
  myComparator>
    priorityQueue;

  //声明元组
  tuple<int, int, string> tuple1;

  // 初始化元组
  tuple1 = make_tuple(0, 0,
                      "Geeks");

  //将元组推入
  //优先队列
  priorityQueue.push(tuple1);

  //声明元组
  tuple<int, int, string> tuple2;

  // 初始化元组
  tuple2 = make_tuple(0, 1,
                      "Programming");

  //将元组推入
  //优先队列
  priorityQueue.push(tuple2);

  //声明元组
  tuple<int, int, string> tuple3;

  // 初始化元组
  tuple3 = make_tuple(1, 2,
                      "Geeks");

  //将元组推入
  //优先队列
  priorityQueue.push(tuple3);

  //声明元组
  tuple<int, int, string> tuple4;

  // 初始化元组
  tuple4 = make_tuple(1, 3,
                      "Programming");

  //将元组推入
  //优先队列
  priorityQueue.push(tuple4);

  //调用打印函数
  print(priorityQueue);

  return 0;
}  

输出

[ 1 3 Programming]
[ 1 2 Geeks]
[ 0 1 Programming]
[ 0 0 Geeks]

在上面的程序中，对于一对元组，首先比较元组的第二个元素，如果这个值相等，则比较第一个元素，如果两个元组的第一个元素相等，则比较第三个元素。否则，具有更大元素的元组将成为顶部元素。