priority

2023-06-11 18:33| 来源: 网络整理| 查看: 265

priority_queue 1. priority_queue的介绍及使用1.1 priority_queue的介绍1.2 priority_queue的使用1.2.1 constructor(构造)1.2.2 empty1.2.3 size1.2.4 top1.2.5 emplace1.2.6 push、pop、swap 1.3 数组中第K个大的元素 2.priority_queue的深度剖析及模拟实现

在这里插入图片描述

1. priority_queue的介绍及使用 1.1 priority_queue的介绍

在C++中，priority_queue是一个容器适配器，它提供了常数时间的最大元素查找。它通常实现为堆。堆是一种数据结构，其中最大（或最小）元素始终位于顶部。priority_queue是一个模板类，定义在头文件中。它有三个模板参数：元素类型、容器类型和比较函数类型（可选）。默认情况下，它使用std::vector作为其底层容器。

1.2 priority_queue的使用

Member functions: 在这里插入图片描述

1.2.1 constructor(构造) int main () { int myints[]= {10,60,50,20}; priority_queue q1; priority_queue q2(myints,myints+4); priority_queue q3(myints,myints+4); return 0; } q1为空。q2包含为定义的四个整数，60（最高）位于其顶部。q3具有相同的四个整数，但由于它使用而不是默认值（即），因此它将 10 作为其顶部元素添加新元素。这个新元素是就地构造的，作为其构造函数的参数传递。 1.2.2 empty

在C++ STL中，empty()函数是一个预定义函数，用于检查集合是否为空。如果集合为空，则返回true（1），如果集合不为空，则返回false（0）。对于空的容器，empty()函数返回true，否则返回false 。

#include #include using namespace std; int main() { int a[] = { 3,6, 2,8,1 }; priority_queue q1; priority_queue q2(a, a + 5); cout priority_queue mypq; mypq.emplace("orange"); mypq.emplace("strawberry"); mypq.emplace("apple"); mypq.emplace("pear"); cout priority_queue q1; q1.push(1); q1.push(2); q1.push(3); priority_queue q2; q2.push(4); q2.push(5); q2.push(6); swap(q1, q2); cout cout priority_queue deq(nums.begin(), nums.end()); while(--k) { deq.pop(); } return deq.top(); } };

在这里插入图片描述

第三种方法：建立一个有K个元素的优先级队列(小堆)，然后遍历nums，大的元素进队列，最后队列的top就是所求元素

class Solution { public: int findKthLargest(vector& nums, int k) { priority_queue deq(nums.begin(), nums.begin() + k); for (size_t i = k; i deq.pop(); deq.push(nums[i]); } } return deq.top(); } };

在这里插入图片描述

2.priority_queue的深度剖析及模拟实现

priority_queue有三个模板参数：元素类型、容器类型和比较函数类型（可选）。默认情况下，它使用std::vector作为其底层容器，而且不需要迭代器，所以实现较为简单。

namespace k { template class priority_deque { public: size_t size() { return _con.size(); } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() { return _con[0]; } bool empty() { return _con.empty(); } protected: void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (_con[parent] break; } } } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child ++child; } if (_con[parent] break; } } } private: Container _con; }; }

如上为priority_queue的实现，其中向上调整(adjust_up)、向下调整(asjust_down)调整的是大堆，是写死的，如过要小堆，则怎么弄？这就是模版的细节之处。只要定义一个比较方式，就可以解决。

namespace k { template struct less { bool operator()(const T& x, const T& y) { return x return x > y; } }; template class priority_deque { public: size_t size() { return _con.size(); } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() { return _con[0]; } bool empty() { return _con.empty(); } protected: void adjust_up(size_t child) { Compare com; size_t parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child ++child; } if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } private: Container _con; }; }

如上定义两个仿函数，然后模版引入就可以实现。

【本文地址】

公司简介

联系我们