堆（优先级队列）

一、STL priority_queue

C++ 的 STL 中提供了“优先队列”这一容器，它和普通的 FIFO 队列都定义在 <queue> 中，有 push() 和 pop() 过程，分别表示“往队列里加入新元素”和“从队列里删除队首元素”

唯一的区别是，在优先队列中，元素并不是按照进入队列的先后顺序排列，而是按照优先级的高低顺序排列

换句话说，pop() 删除的是优先级最高的元素，而不一定是最先进入队列的元素。正因为如此，获取队首元素的方法不再是 front()，而是 top()

定义优先队列最简单的方法是 priority_queue<类型名> q，它利用元素自身的“小于”操作符来定义优先级

例如，在 priority_queue<int> q 这样的优先队列中，先出队的总是最大的整数

1、重载“<”操作符来定义优先级

如果优先队列的元素类型是结构体，可以通过在结构体中重载“<”操作符的方法来修改优先队列的优先性

struct Node {
    int val;
    bool operator < (const Node& a) const {
        return a.val < val;     //按 val 由小到大排列
    }
};

2、重载“()”操作符来定义优先级

如果优先队列的元素不是结构体类型，则可以通过重载“()”操作符的方式来定义优先级

当然，元素是结构体类型，也可以通过重载“()”操作符的方式来定义优先级，而不是一定要在结构体内重载“<”操作符才行

//“个位数大的优先级反而小”的整数优先队列
struct cmp {
    bool operator () (const int a, const int b) {
        return (a%10) > (b%10);
    }
};

priority_queue<int, vector<int>, cmp> Q;

二、堆（二叉堆）（heap）

参考：http://blog.csdn.net/morewindows/article/details/6709644/

堆就是像下图这样的二叉树

堆通常是一个可以被看做一棵树的数组对象

堆总是满足下列性质：

• 就优先级而言，堆顶以外的每个节点都不高（大）于其父节点，此即所谓的“堆序性”
• 堆总是一棵完全二叉树

除此之外，树的节点是按从上到下、从左到右的顺序紧凑排列的

1、大顶堆与小顶堆

由堆序性不难看出，堆中优先级最高的词条必然始终处于堆顶位置。因此，堆结构的获得优先级最高的词条的操作总是可以在 O(1) 时间内完成

堆序性也可对称地约定为“堆顶以外的每个节点都不低（小）于其父节点”，此时同理，优先级最低的词条，必然始终位于堆顶位置

为以示区别，通常称前（后）者为大（小）顶堆

小顶堆和大顶堆是相对的，而且可以相互转换

2、堆的存储

尽管二叉树不属于线性结构，但作为其特例的完全二叉树，却与向量有着密切的对应关系

所以我们一般用一维数组来存储堆，按照层次遍历序列，对完全二叉树节点做编号，这样我们就可以将堆定义为满足某种关系的 n 个元素的序列 {k1, k2, ki, ..., kn}

那么第 1 个元素存储的就是堆顶的元素，每个节点的左右子节点分别为第 i*2 和 i*2+1 个元素，堆顶以外的每个节点的父节点为第 i/2 个元素

3、堆的插入

void Insert(int key)
{
    num[++Size] = key;
    int pos = Size;
    while (pos > 1 && num[pos] < num[pos>>1]) {
        swap(num[pos>>1], num[pos]);
        pos >>= 1;
    }
}

4、堆的删除

按定义，堆中每次都只能删除堆顶元素

void Delete(void)
{
    num[1] = num[Size--];
    int pos = 2;
    while (pos <= Size) {
        if (pos <= Size-1 && num[pos+1] < num[pos]) {
            ++pos;
        }
        if (num[pos] < num[pos>>1]) {
            swap(num[pos], num[pos>>1]);
            pos <<= 1;
        } else {
            break;
        }
    }
}

5、堆化数组

对于序列 {9, 12 17, 30, 50, 20, 60, 65, 4, 19} ，我们要如何对其进行堆化操作

很明显，对每个叶子节点来说，它已经是一个合法的堆了

我们只要从第 5 个元素 50 开始调整，然后再取 60, 17, 12, 9 分别进行调整，如图所示

void Build_Heap(void)
{
    for (int i = n/2; i >= 1; --i) {
        int j = (i << 1);
        while (j <= n) {
            if (j+1 <= n && num[j+1] < num[j]) {
                ++j;
            }
            if (num[j] < num[j>>1]) {
                swap(num[j], num[j>>1]);
                j <<= 1;
           } else {
                break;
            }
        }
    }
}

6、堆排序

我们先建好一个大顶堆，规定数值越大的元素的优先级越高，那么堆顶元素必然为最大的元素

将堆顶元素与第 n 个元素交换，然后再对第 1 个元素到第 n-1 个元素进行调整，重新恢复为堆，重复这样的操作直到交换堆顶元素和第 2 个元素

这就是一个堆排序的过程

由于每次都将当前区间最大的整数放到后面的有序区间，故整个操作完成后数组就是一个从小到大排列的有序序列了

时间复杂度：O(n * logn)

void Heap_Sort(void)
{
    Build_Heap();
    for (int i = n; i >= 2; --i) {
        swap(num[i], num[1]);
        int j = 2;
        while (j <= i-1) {
            if (j+1 <= i-2 && num[j+1] > num[j]) {
                ++j;
            }
            if (num[j] <= num[j>>1]) {
                break;
            }
            swap(num[j], num[j>>1]);
            j <<= 1;
        }
    }
}

void Build_Heap(void)
{
    for (int i = n/2; i >= 1; --i) {
        int j = (i << 1);
        while (j <= n) {
            if (j+1 <= n && num[j+1] > num[j]) {
                ++j;
            }
            if (num[j] > num[j>>1]) {
                swap(num[j], num[j>>1]);
                j <<= 1;
           } else {
                break;
            }
        }
    }
}

三、STL heap

参考：http://blog.csdn.net/morewindows/article/details/6967409

http://blog.csdn.net/lwfcgz/article/details/8760092

1、make_heap

STL 默认建立的是最大堆，对int类型，可以在第三个参数传入greater<int>() 得到最小堆

2、push_heap

需要先在末尾加入数据，再进行调用

3、pop_heap

调用后需要删除末尾数据

4、sort_heap

排序以后就不是一个合法的堆了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cmath>
#include <cctype>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const ull mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int maxn = 1e5 + 10;
int num[maxn];
int n;

int main()
{
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif // __AiR_H
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num[i]);
    }
    vector<int> V(num, num+n);

    make_heap(V.begin(), V.end());
    printf("initial max heap   : %d\n", V[0]);

    pop_heap(V.begin(), V.end());
    V.pop_back();
    printf("max heap after pop : %d\n", V[0]);

    V.push_back(99);
    push_heap(V.begin(), V.end());
    printf("max heap after push: %d\n", V[0]);

    sort_heap(V.begin(), V.end());
    printf("final sorted range :");
    for (int i = 0; i < n; ++i) {
        printf("%d ", V[i]);
    }
    printf("\n");
    return 0;
}

/*
input :
9
1 4 7 2 5 8 3 6 9

output :
initial max heap   : 9
max heap after pop : 8
max heap after push: 99
final sorted range :1 2 3 4 5 6 7 8 99
*/

四、其它

参考：http://www.xuebuyuan.com/582423.html?mobile=1

1、d 叉堆