一、STL自带堆：priority_queue

stack与queue注意事项：

1 stack不允许有遍历行为，stack也不提供迭代器。SGI STL便以deque作为缺省情况下stack底部结构，称之为adapter（配接器）

2 除了deque之外，list也是双向开口的数据结构

3 queue与stack的情况类似，不提供迭代器，也可以以list作为底层容器,默认为deque。

priority_queue的底层实现——heap

缺省情况下priority_queue优先级队列是利用一个max-heap最大堆完成，后者是一个以vector表现的完全二叉树。

“依权值高低自动递减排序”

1 priority_queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高(也即数值最高，最大堆)的元素开始取。

2 二叉堆，完全二叉树，（由数组实现，数组来存储所有节点,2*i+1,2*i+2,但是由于动态改变大小，所以不用array用vector）插入O(logN)，删除O(logN)

二、例子

1.先给一个简单应用的例子，这个和容器的用法差不多。

#include <iostream>
#include <queue>
using namespace std; 

int main()
{
    priority_queue<float> q;    //默认的是大顶堆 

    // insert three elements into the priority queue
    q.push(66.6);
    q.push(22.2);
    q.push(44.4); 

    // read and print two elements
    cout << q.top() << ' ';         //queue当中是q.front();
    q.pop();
    cout << q.top() << endl;
    q.pop(); 

    // insert three more elements
    q.push(11.1);
    q.push(55.5);
    q.push(33.3); 

    // skip one element
    q.pop(); 

    // pop and print remaining elements
    while (!q.empty())
    {
        cout << q.top() << ' ';
        q.pop();
    }
    cout << endl;
}

2.下面是将节点存在优先队列中的两种方式

最好的方式：这个简洁！

struct Node
{
    int x,y;
    bool operator <(Node a) const  {  return y < a.y; }
    bool operator >(Node a) const  {  return y > a.y; }
};
    priority_queue<Node> A;                    //大根堆
    priority_queue<Node, vector<Node>, greater<Node> > B;    //小根堆 

方式一：

struct Node
{int adj;
 int val;
 friend  bool operator<(const Node &a,const Node &b) { return  a.val > b.val; }
};
priority_queue<Node>Q; 

方式二：（cmp将结构体以val由大到小排列，组成大根堆）一般也用这个！

struct Node
{int adj;
 int val;
};
struct cmp
{bool operator()(Node a,Node b) { return  a.val > b.val; }
};
priority_queue<Node,vector<Node>,cmp>Q; 

方式三：

struct TMax
{
    TMax(int tx):x(tx){}
    int x;
}; 

struct TMin
{
    TMin(int tx):x(tx){}
    int x;
}; 

bool operator<(const TMax &a, const TMax &b)
{
    return a.x<b.x;
} 

bool operator<(const TMin &a, const TMin &b)
{
    return a.x>b.x;
} 

priority_queue<TMax> hmax;    //大顶堆
priority_queue<TMin> hmin;    //小顶堆 

3.下面是将指针存在优先队列中的方式

struct Node
{
     short f;
     short d;
     short fishs;
     short times;
     short i;
}; 

struct PCmp
{
    bool operator () (Node const *x, Node const *y)
    {
        if(x->f == y->f)
            return x->i > y->i;
        return x->f < y->f;
    }
}; 

priority_queue<Node*, vector<Node*>, PCmp > Q;

注：在这种情况下往往可以预分配空间以避免new带来的麻烦。例如：堆中定义Node Qt[26]， 栈中的使用则为Node *tmp1 = Qt。

经过测试，在优选队列当中存指针进行一系列操作要比存节点进行一系列操作快一些。

 

注：

1. less<class T>这是大顶堆，按值大的优先，值大的在最上面。greater<class T>这是小顶堆，按值小的优先，值小的在最上面。
2. 自定义cmp如果还有不明白的看这里：

   struct cmp
   {
    bool operator()（const int &a,const int &b）//这里的&是引用
    {
     return a>b;//最大堆
     return a<b;//最小堆
    }
   };
   priority_queue< int, vector<int>, cmp >

3. 还是自定义cmp函数，注意，一般ACM中用结构体内含“bool operator()（const int &a,const int &b）”。这其实等价于Class cmp，不过更省事，当然也不规范（不需要规范）。
4. return就是希望如何排列为true。如果希望由大到小，就将大到小的情况return；反则亦然。和sort的自定义cmp是一样的。

三、STL另外的heap

STL heap包括：

1 push_heap算法：新元素插入在底层的vector的end()处。向上回溯

2 pop_heap算法：把堆顶元素和数值末尾元素调换，向下回溯。

3 sort_heap算法：持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素。执行过后，原来的heap不再是个合法的heap了。

4 meak_heap算法：找出第一个需要重排的子树头部(n-2)/2，从当前位置向根节点回溯。