做营销策划要用到哪些网站,无广告免费追剧软件,电子商务网站平台开发建设方案,岳池住房和城乡建设厅网站priority_queue翻译过来就是优先队列#xff0c;其实就是我们数据结构中的堆。堆这个东西之前也说过#xff0c;它分为大根堆和小根堆#xff0c;它的底层是一个类似数组的连续的空间#xff0c;逻辑结构是一个完全二叉树#xff0c;这个完全二叉树如果是小根堆的话父亲小… priority_queue翻译过来就是优先队列其实就是我们数据结构中的堆。堆这个东西之前也说过它分为大根堆和小根堆它的底层是一个类似数组的连续的空间逻辑结构是一个完全二叉树这个完全二叉树如果是小根堆的话父亲小于孩子。两兄弟之间没有关系两个比较关键的操作就是向上调整和向下调整在建堆和出数据的时候很关键。 下面我们来复习一下向上调整和向下调整 void adjustup(int* a, int n) {for (int i 1; i n; i) {int j i;int parent (j - 1) / 2;while (parent 0) {if (a[j] a[parent]) {swap(a[j], a[parent]);}else break;j parent;parent (j - 1) / 2;}}
}void adjustdown(int* a, int n, int pos) {int child pos * 2 1;while (child n) {if (child 1 n a[child] a[child 1])child;if (a[child] a[pos])swap(a[child], a[pos]);else break;pos child;child child * 2 1;}
} 这就是我们之前学的我们要排升序要建大堆排降序要建小堆那我们来看看C库里是怎么弄的 这也是一个容器适配器容器的缺省值用的vector因为这种结构建起堆来是比较容易的这跟我们原来学的用数组也是一样的道理第三个模板参数是一个用来比较的模板参数这个参数是一个类缺省值是用的less默认是建大堆。文档中也有介绍 我们要是想建小堆则要改变第三个模板参数而它是一个类所以我们要传一个类进去就是我们上边的greaterint我们要传第三个就要传第二个这是缺省值的语法规则限制的给缺省值要从右向左依次给传参数时从左向右依次匹配。 我么说了第三个模板参数传了一个类一个类怎么实现一个比较函数的功能呢我们之前不就是传一个函数指针比如qsort用回调函数 因为一个类它并不是函数所以叫仿函数或者叫函数对象它是一个类实例化的一个对象有函数的功能我们也可以随随便便写一个仿函数 所以它的关键就是重载了括号使它的对象可以用括号这个操作符从而就像函数一样我们下边模拟实现的时候建大堆还是小堆都是跟库中一样通过传一个类来实现的 下面是一个找数组中最大的第k个数的问题用C写就方便了很多 class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint, vectorint, greaterint pq(nums.begin(),nums.begin() k);auto it nums.begin() k;while (it ! nums.end()) {if (*it pq.top()) {pq.pop();pq.push(*it);}it;}return pq.top();}
}; 用法讲完了下面我们来模拟实现一下 namespace jxh {templateclass T, class container vectorT, class compare lessTclass priority_queue {public:void adjustup(int child) {compare com;int parent (child - 1) / 2;while (parent 0) {if (com(_con[child] , _con[parent])) {std::swap(_con[child], _con[parent]);}else break;child parent;parent (child - 1) / 2;}}void adjustdown(int parent) {compare com;int n _con.size();int child parent * 2 1;while (child n) {if (child 1 n com(_con[child 1], _con[child]))child;if (com(_con[child] , _con[parent]))std::swap(_con[child], _con[parent]);else break;parent child;child child * 2 1;}}void push(const T x) {_con.push_back(x);adjustup(_con.size() - 1);}void pop() {std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T top() {return _con[0];}bool empty() {return _con.empty();}size_t size() {return _con.size();}private:container _con;};
}
