C++_STL---priority_queue

priority_queue的相关介绍

1. 优先级队列是一种容器适配器，根据严格的排序标准，它的第一个元素总是它所包含的元素中最大(小)的。
2. 该容器适配器类似于堆，在堆中可以随时插入元素，并且可以检索最大(小)堆元素(优先级队列中位于顶部的元素)。
3. 优先级队列被实现为容器适配器，容器适配器即 将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先级队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应可以通过随机访问迭代器访问。
5. 标准容器类vector和deque皆满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

更多关于priority_queue的详细内容，请点击priority_queue的文档介绍

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。 

函数声明	接口说明
priority_queue() priority_queue(InputIterator first, InputIterator last)	无参构造 迭代器区间初始化构造
empty()	检查优先级队列是否为空
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

// 使用举例(和queue类似)
int arr[] = { 3,2,7,6,0,4,1,9,8,5 };
// 迭代器区间初始化
priority_queue<int> pq1(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!pq1.empty())              // 判断优先级队列是否为空
{cout << pq1.top() << " ";     // 获取栈顶元素pq1.pop();                    // 删除元素
}
cout << endl;
// 结果为：9,8,7,6,5,4,3,2,1,0 

上述代码结果默认是大堆(降序)，其默认仿函数为less()，若想得到升序序列，只需改变仿函数为greater()即可。

// 改变仿函数
priority_queue<int, vector<int>, greater<int>> pq1(arr, arr + sizeof(arr) / sizeof(int));

priority_queue的底层实现

ps.  默认情况下，创建的是大堆，其底层按照小于号比较

// 迭代器区间初始化
priority_queue(InputIterator first, InputIterator last)
{while (first != last){_con.push_back(*first);++first;}//建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i); //向下调整算法}
}

// 向上调整算法
void AdjustUp(int child)
{int parent = (child - 1) / 2;while (child > 0){// 使用仿函数if (_comFunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
// 插入
void push(const T& x)
{_con.push_back(x);AdjustUp(_con.size() - 1);
}

// 向下调整算法
void AdjustDown(int parent)
{size_t child = parent * 2 + 1;while (child < _con.size()){// 使用仿函数if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1])){++child;}if (_comFunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
//删除
void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}