STL priority_queue的介绍与使用

priority_queue：优先级队列。她有别于以往我们理解的“先进先出”的queue，她是优先级高者先出，内部自己帮你排序，默认是堆排序。两者有何相似与不同：

相似处：

1、都只允许最底端加入元素(push)，最顶端弹出元素(pop)

2、都没有迭代器，不能遍历访问(当然如果全部倒出来访问，这是防止不了的)

3、两者都支持判空(empty)和获取大小(size)的操作

不同之处：
       1、priority_queue只允许访问最顶端元素(priority_queue.top)， 而queue可以访问首尾queue.front和queue.back.

2、priority_queue内部采取的最大堆的算法，每次弹出的元素都是优先级最高的元素，并且加入或弹出元素，内部元素都需要重新调整结构，说白了就是排序；

     顺便唠叨一下堆排序：特性：不稳定的排序，时间复杂度为O(nlogn)，并且对原始记录的排序状态不敏感，无论最好，最坏和平均，时间复杂度都是O(nlogn)。
通常在对平均时间要求严格，数据量大，并且出现最坏情况的可能性大的场景，可以考虑使用堆排序。

3、由于需要计算优先级，所以如果不是基本数据类型，则必须重载operator

要会用，还得知道她有哪些API

priority_queue(InputIterator frist, InputIterator last) /*基本数据类型使用*/
priority_queue(InputIterator frist, InputIterator last, const Compare &x)/*复杂数据类型，需要提供比较函数*/
/*补充一点：基本数据类型的指针可以作为InputIterator传入，例子如下：
int ia[9] = {0,1,2,3,4,5,6,7,8};
priority_queue ipq(ia, ia+9);
*/
bool empty()/*判空*/
size_type size()/*队列大小*/
const_reference top()/*获取顶端元素，注意这里不会弹出*/
void push(const value_type &x)/*增加元素*/
void pop()/*弹出元素*/

什么情况下，我们会需要用到priority_queue？来看个实际的例子：

题目来源：

Merge k Sorted Lists

 

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    struct cmp
    {
           /*题目已经定义ListNode的结构，并且没有重载<，所以只能采取这种方式了*/
        bool operator ()(const ListNode *node1, const ListNode *node2)
        {
                return node1->val>node2->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int size = lists.size();

        ListNode head(0);
        ListNode *res = &head;
        ListNode *tmp = NULL;
        priority_queue<ListNode*, vector<ListNode*>, cmp> que;
          . /*priority_queue中的三个参数，后两个可以省去，因为有默认参数，但是如果有第三个参数的话，必定要写第二个参数*/
        if(size == 0)
            return NULL;

        for(int i=0; i<size; ++i)
            if(lists[i])
                que.push(lists[i]);

        while(!que.empty())
        {
            tmp = que.top();
            que.pop();
            res->next = tmp;
            res = tmp;

            if(tmp->next)
                que.push(tmp->next);
        }
        return head.next;
    }
};

Note：priority_queue通常不被认为是容器，而认为是容器适配器.底部容器可以是vector、list等容器，本文没有详细讨论。在这个实例里，我是看上了他的堆排序，呜呜~~~

STL总是给人一种站在巨人肩上的感觉，爽