在刷题过程中,我们会遇到求第K大元素这样的问题,其中一种效率还可以的做法是使用优先级队列实现,底层数据结构一般是堆。我估计很多同学搞不清楚优先级队列和堆的区别,不服的举手,这个问题我们最后讨论,我们先来仔细看看C++标准库中priority_queue的用法,这是本文的重点。
priority_queue这个类在STL的queue文件中,有如下方法:
首先是top函数,这个函数返回堆顶的元素,大堆返回最大的元素,小堆返回最小的元素。
其次是大小接口,empty函数是检查容器是否为空,size返回元素的个数。
然后最重要的是修改操作,push函数可以插入元素到队列中,emplace函数也是插入,这2个有啥区别呢?注意C++11的容器操作很多都加了emplace相关的函数,这个函数更加高效,可以减少拷贝,一般情况下优先使用emplace函数,性能和内存都会好些。
修改操作pop就是将堆顶元素删除掉。
swap操作有点特别,如下例子:
// priority_queue::swap
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main ()
{
std::priority_queue<int> foo,bar;
foo.push (15); foo.push(30); foo.push(10);
bar.push (101); bar.push(202);
foo.swap(bar);
std::cout << "size of foo: " << foo.size() << '\n';
std::cout << "size of bar: " << bar.size() << '\n';
return 0;
}
这个例子会输出:
size of foo: 2
size of bar: 3
也即是说,swap是交换两个容器的数据,这种操作一般可以在外部自己实现,标准库提供了这个接口看了是考虑性能。
优先级队列的功能就这些,下面我们来看看构造函数:
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
模板有3个参数,第一个参数是类型,第二个参数是底层放数据的容器类型,第三个参数是比较函数,上面是将cmp这个参数传进去作为比较函数。
基本上就这些内容,如何实现求第K大的树呢?我们只需要让这个队列一直保留K个元素,堆顶的元素就是第K大的。
下面我们来讨论一下优先级队列和堆的区别。
堆是一种数据结构,是一种非常确定的数据结构,堆顶是最值,就像链表、队列、栈这种数据结构。
而优先级队列是一种抽象的数据类型,只给了是什么的解释(what),没有给具体实现(how),只不过恰巧优先级队列大部分情况都是用堆实现的。