poj1442中如何运用优先队列实现高效排序？

本文共计602个文字，预计阅读时间需要3分钟。

历经艰辛终于解决了这个问题，原本用STL可以这么简单~思路如下：用STL的两个优先队列，big队列优先弹出最小的，small队列优先弹出最大的，若要求数第i小的数字，只需满足small队列中有i个元素即可。

历经磨难终于解决了这题，原来用stl可以这么简单~

这题的思路:

用stl弄2个优先队列，big队列优先弹出最小的，small队列优先弹出最大的，若要求第i小的数字，只要满足small队列里有i个元素，且small队列的top比big队列的top小，则small的top就是第i小的数字。

关于优先队列记住下面这些东西：

模板原型：

priority_queue<T,Sequence,Compare>

T:存放容器的元素类型

Sequence:实现优先级队列的底层容器，默认是vector<T>

Compare:用于实现优先级的比较函数，默认是functional中的less<T>，即默认是弹出最大的元素

若要创建弹出最小元素的优先队列，形式是priority_queue<int,vector<int>,greater<int> >big;

比较函数当然可以自己去定义。