堆排序（优先队列）

堆（二叉堆）

此处堆不是存储中的堆，并且满足一下几个性质：

1.每个节点在此子树中最大（最小）。

2.此树为一颗完全二叉树。

数组本身就满足完全二叉树，假设1为根节点那么子节点为2,3, 2的子节点为4,5...那么只需要将这个完全二叉树调整至满足第一个条件就是一个堆了，调整时，叶子节点都是满足条件，然后从最后一个存在子节点的节点开始调整子树，从后调整的好处是每次调整当前节点时子树都是满足堆的性质，就只需要将此节点调整至相应的位置。

堆排序其实是将数组调整堆后，取第一个数字就是整个数组中最大（最小）值，将最后一个值移动到第一个位置就值需要将第一位置调整成堆，直至没有元素那么取出的序列就是一个有序的序列。

当求多次a[1..k]的最大（最小）元素时，如果每次都排序一次复杂度就高了，然而堆就可以实现这一点，当只有一个节点时，本省就是一个堆，每增加一个节点将其插入至最后，而前面的节点已经是一个堆了，只需要将此节点调整至相应的位置即形成一个堆，求最大（最小）值时直接取第一个值就行了，这就是优先队列的实现原理，只不过库中优先队列基本上实现的是模板（即任何类型都可以用只不过需要覆写函数或重载运算符）。

优先队列最典型的用法就是建哈夫曼树，哈夫曼树每次从所有权值中取最小的两个构建一个节点，再将这两个权值的和加入权值集合中，再取两个最小的构建节点，这种动态求最大（最小）值用优先队列就比较快，像bfs，Dijkstra，Prim等算法都有用到优先队列来辅助。

当然其实建哈夫曼树更简单的方法是排一下序用两个数组辅助就可以了，这样的常数更小。

struct priority_Queue
{
    int a[maxn], cnt;
    void init ( )
    {
        cnt = 0;
    }
    bool empty ( )
    {
        return cnt == 0 ? true : false;
    }
    void adjust ( int p )
    {
        int x = a[p], j = p;
        while ( j <= cnt )
        {
            j = j*2;
            if ( j+1 <= cnt && a[j] > a[j+1] )
                j ++;
            if ( j > cnt || a[j] > x )
                break ;
            a[p] = a[j];
            p = j;
        }
        a[p] = x;
    }
    int top ( )
    {
        int x = a[1];
        return x;
    }
    void pop ( )
    {
        a[1] = a[cnt];
        cnt --;
        adjust ( 1 );
    }
    void up_adjust ( int p )
    {
        int x = a[p], j = p;
        while ( j > 0 )
        {
            j /= 2;
            if ( j <= 0 || a[j] <= x )
                break ;
            a[p] = a[j];
            p = j;
        }
        a[p] = x;
    }
    void push ( int x )
    {
        cnt ++;
        a[cnt] = x;
        up_adjust ( cnt );
    }
};