C++中优先队列priority_queue的基础用法

一时失言乱红尘 2022-12-06 05:21 188阅读 0赞

### 文章目录 ###

*  前言
 *  头文件
 *  结构定义
 *  队列排序
 *  优先队列使用
 *   *  实现排序
     *  取出数组中最大的k个数
     *  自定义结构
     *  自定义比较函数的另一种写法
 *  常用函数
 *  总结

# 前言 #

学习优先队列之前先看个单词队列 queue， 这个单词的读法很多人都能读对吧，音标是 `/kjuː/` ，再看一个双端队列 deque，它的音标是 `/dek/`，应该有人读错了吧，反正我是没读对，刚开始看见一次错一次，现在还好了，基本能记住怎么读了，可是这些队列怎么用呢？

队列就不用多说了，一个先进先出的经典数据结构，那么优先队列是个什么鬼，其实它就是在队列的基础上加上优先两个字，想想怎样才能优先呢？没错——排队！只有排好了队伍才会有落后和优先之分，否则一团乱糟糟的，怎么才能分出优先的，所以优先队列一定应用了排序。

可是排序要怎样实现呢？其实排序这个底层逻辑你是不用管的，你只要把想要的数据放到优先队列里，然后取出的必定是当前状态下最优的，当然，究竟什么是最优的条件是需要你来设定的，也就是说我们需要定义排序的规则。

# 头文件 #

优先队列 priority\_queue 是队列 queue 的一个变种，头文件是`#include <queue>`，使用优先队列必须要包含这个头文件。

# 结构定义 #

优先队列的结构定义是一个模板类，需要提供三个类型参数：

template<
        class T,
        class Container = std::vector<T>,
        class Compare = std::less<typename Container::value_type>
    > class priority_queue;

从定义可以看出，虽然要结构是三个参数，但是后两个参数带了默认值，所以针对于普通的数据类型，一般情况下指提供第1个参数就可以了，比如 `priority_queue<int>` 实际上等价于 `priority_queue<int, vector<int>, less<int>>`。

这三个参数的含义分别为：数据类型，容器类型和比较函数，实际上优先队列就是维护了一个装有 `T` 类型元素的容器 `Container`，并在入队和出队时对容器内元素使用 `Compare` 比较函数进行了排序。

这3个参数还要满足一定的要求，并且在使用过程中有些注意事项：

*  如果类型 `T` 和 `Container` 容器中元素类型不一致，那么行为未定义，所以要避免这种情况。
 *  `Container` 必须是序列容器，其实C++中序列容器很多的，比如`std::array`、`std::vector`、`std::deque`、`std::list`等
 *  `Container` 还必须要支持随机访问，并且有 `front()`、`push_back()`、`pop_back()` 等函数

这样来看只有 `std::vector`、`std::deque` 满足容器条件了，而优先队列中使用的默认参数也是 `std::vector`。

# 队列排序 #

一直在说优先队列里使用了排序，而常用的容器是 `std::verctor`，那么究竟用的是什么排序，又是在什么时候进行的排序呢？实际上这里的排序并不是我们通常拿到数据后使用的冒泡排序、快速排序等，优先队列中的排序本质上是堆排序，但是它不是每次都进行完整的堆排序，而是通过 `Container` 维护了一个堆结构，每次入队和出队时都进行一次堆调整，所花时间为 `log(n)`，所以用在数据量大的地方，速度比较快。

# 优先队列使用 #

当我们大概了解了优先队列的原理后，可以通过使用来进一步熟悉这个结构，下面来看几个例子。

## 实现排序 ##

#include <iostream>
    #include <queue>
    using namespace std;
    
    void common_sort()
    { 
        int source_data[10] = { 3, 5, 8, 1, 10, 2, 9, 15, 13, 16};
    
        // 默认大根堆，实现由大到小排序
        priority_queue<int> q;
        for (auto n : source_data) q.push(n);
    
        while (!q.empty()) { 
            cout << q.top() << endl;
            q.pop();
        }
    }

`priority_queue<int>` 默认构建的是一个大根堆，所以每次从头取数据得到的是一个从大到小的队列排序

albert@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o commonsort -std=c++11
    albert@home-pc:/mnt/c++/datastruct$ ./commonsort
    16
    15
    13
    10
    9
    8
    5
    3
    2
    1

如果是完整排序使用优先队列就有些麻烦了，还不如直接调用 `std::sort` 函数，但是如果只取部分数据的话，优先队列还是非常方便快速的，比如下面这个问题。

## 取出数组中最大的k个数 ##

这是一个经典的算法题，最容易想到的办法就是遍历，先找到最大的，然后排出这个数再找到最大的，这样找k次就好了，所需时间大概表示为 `O(kN)`。

还有一个方法是排序，使用 `std::sort` 排序后，然后依次取出前 k 个数就行了，排序使用快速排序的话可以达到所需时间为 `O(Nlog(N))`，其实这样已经很优秀了，但是还可以通过优先队列来加速，下面来写一下代码：

#include <iostream>
    #include <queue>
    using namespace std;
    
    void max_k_num()
    { 
        int source_data[10] = { 3, 5, 8, 1, 10, 2, 9, 15, 13, 16};
        int k = 5;
    
        // 小根堆
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto n : source_data) { 
            if (q.size() == k) { 
                if (n > q.top()) { 
                    q.pop();
                    q.push(n);
                }
            }
            else q.push(n);
        }
    
        while (!q.empty()) { 
            cout << q.top() << endl;
            q.pop();
        }
    }

这里是定义了一个小根堆，堆顶是最小值，当有新元素大于堆顶元素时，并且队列中元素等于k个，需要移除堆顶元素，然后插入新的元素，这样就能保证优先队列中始终拥有最大的k个数，运行结果如下：

albert@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o max_k_num -std=c++11
    albert@home-pc:/mnt/c++/datastruct$ ./max_k_num
    9
    10
    13
    15
    16

因为这里控制堆的规模最大为k，所以这个算法的执行时间大概是`O(Nlog(k))`，绝大多数情况是优于快速排序的。

## 自定义结构 ##

使用优先队列时常常要用到自定义结构，这时候就需要自己来写比较函数了，比如输出成绩最好的三个人的信息：

#include <iostream>
    #include <queue>
    using namespace std;
    
    struct student { 
        string name;
        int score;
    };
    
    struct cmp_custom { 
        bool operator()(student& x, student& y) { 
            return x.score > y.score;
        }
    };
    
    void max_k_score()
    { 
        vector<student> stu_list = { { "Andy", 89}, { "Bella", 79}, { "Cary", 92}, { "Dick", 60}, { "Ray", 70}};
        int k = 3;
    
        // 小根堆
        priority_queue<student, vector<student>, cmp_custom> q;
        for (auto stu : stu_list) { 
            if (q.size() == k) { 
                if (stu.score > q.top().score) { 
                    q.pop();
                    q.push(stu);
                }
            }
            else q.push(stu);
        }
    
        while (!q.empty()) { 
            cout << q.top().name << ":" << q.top().score << endl;
            q.pop();
        }
    }

输出结果如下，每个人的名字后面跟着分数，结果是分数最大的3个人的信息：

albert@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o max_k_score -std=c++11
    albert@home-pc:/mnt/c++/datastruct$ ./max_k_score
    Bella:79
    Andy:89
    Cary:92

## 自定义比较函数的另一种写法 ##

看到上个例子中自定义比较函数的写法比较怪，一般我们在排序时定义的比较函数使用lambda表达式就可以，而这里是不能直接这样写的，需要多转化一步，写成下面这种形式：

auto cmp = [](student& x, student& y) {  return x.score > y.score; };
    priority_queue<student, vector<student>, decltype(cmp)> q(cmp);

虽然看起来还是有点怪，但总比下面这样要好看的多：

struct cmp_custom { 
        bool operator()(student& x, student& y) { 
            return x.score > y.score;
        }
    };
    priority_queue<student, vector<student>, cmp_custom> q;

# 常用函数 #

优先队列的常用函数与队列类似，常用的有以下这些，如果想了解详细的用法，请戳[在线文档][Link 1]

<table> 
 <thead> 
  <tr> 
   <th align="center">函数名</th> 
   <th align="center">含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/top" rel="nofollow">top</a></td> 
   <td align="center">访问队列的头部元素</td> 
  </tr> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/empty" rel="nofollow">empty</a></td> 
   <td align="center">判断优先队列内是否有元素</td> 
  </tr> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/size" rel="nofollow">size</a></td> 
   <td align="center">返回优先队列内元素个数</td> 
  </tr> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/push" rel="nofollow">push</a></td> 
   <td align="center">向优先队列中插入元素</td> 
  </tr> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/emplace" rel="nofollow">emplace</a></td> 
   <td align="center">在优先队列中构造元素</td> 
  </tr> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/pop" rel="nofollow">pop</a></td> 
   <td align="center">从优先队列头部弹出元素</td> 
  </tr> 
  <tr> 
   <td align="center"><a href="https://en.cppreference.com/w/cpp/container/priority_queue/swap" rel="nofollow">swap</a></td> 
   <td align="center">与其他容器交换元素</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

*  优先队列在一些需要部分排序的场景可以加快访问速度，降低时间复杂度。
 *  优先队列加速所付出的代价就是构建堆结构所需的内存，时间和空间总是一对矛盾共同体
 *  以自定义结构作为元素的优先队列需要单独编写比较函数，可以使用lambda表达式，并用 `decltype(cmp)` 推导类型
 *  需要注意的是这里的优先队列定义，第三个参数的需要的是比较函数的参数类型，而不是比较函数，区分与 `std::sort` 的不同

--------------------

[ ==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<== ][_ _]

--------------------

> 人在比较中奋进，同在比较中消亡，起初面临差距时会奋起直追，但是当努力过后发现距离反而越来越远时，便会麻木懈怠，曾经的努力没有用吗？我觉得不是，努力过不一定会成功，但是努力的过程已经印在了骨子里，这本身就是生活的一部分。你可以选择这条艰苦的路，同样也可以选择跳过，至于跳过时错失了什么，谁又知道呢？毕竟人生无法再来过，重新读档只发生在游戏世界中~

[Link 1]: https://en.cppreference.com/w/cpp/container/priority_queue
[_ _]: https://blog.csdn.net/albertsh/article/details/108439423