当前位置：极客教程 > C++语言 > C++ 教程 > C++中的元组优先队列及其示例

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

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;
}
C++

输出

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

例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;
}
C++

输出

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

元组的最小堆优先队列：

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

示例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;
}
C++

输出

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

示例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;
}
C++

输出

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

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

进一步处理 如何使用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;
}
C++

输出

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

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

例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;
}
C++

输出

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

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

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 教程

登录

找回密码？

注册