堆

堆（Heap）是计算机科学中一类特殊的数据结构，通常是一棵完全二叉树（每个结点只有不超过两个子结点，只有最下边一层从右开始不缺少或连续缺少一段结点，其它层都是满的的树形结构）。

堆的性质有：

1. 堆中某个结点的值总是不大于（或不小于）其父结点的值；
2. 堆通常是一棵完全二叉树。

将根结点最大的堆叫做大根堆，根结点最小的堆叫做小根堆。常见的堆有二叉堆、斐波那契堆等。
左是小根堆，右是大根堆：

堆的定义如下：$n$ 个元素的序列 $A_1,A_2\dots \dots A_i$当且仅当满足下关系时，称之为堆。
$$A_i\le A_{2i},A_i\le A_{2i+1}$$
或者
$$A_{\ge }{A}_{2i},A_i\ge A_{2i+1}(i=1,2,3,4\dots \dots \frac{n}{2}$$
其实这就是把一个节点 $i$ 的左孩子放在 $2i$ 位置，右孩子放在 $2i+1$ 位置，然后满足堆的性质，平常存储堆的时候我们也用这样的方法存储。

堆分别可以插入和弹出元素
Visualgo的二叉堆动画

1. 插入：向堆中插入一个新元素；在数组的最末尾插入新结点。然后自下而上调整子结点与父结点：比较当前结点与父结点，不满足堆性质则交换，使得当前子树满足二叉堆的性质。时间复杂度为 $\mathcal{O}(\log n)$

void push(int A[], int i, int& n) {  // i 为插入的值, n 为插入之前堆的大小
    n++; // 调整大小
    A[n] = i; // 放进堆的最后
    int p = n;
    while (p > 1 && A[p / 2] > A[p]) { // 调整，如果不满足堆的性质，交换父节点和当前节点
        swap(A[p / 2], A[p]);
        p /= 2;
    }
}
1
2
3
4
5
6
7
8
9

2.弹出：删除堆顶元素，再把堆存储的最后那个结点填在根结点处。再从上而下调整父结点与它的子结点。时间复杂度为 $\mathcal{O}(\log n)$

int pop(int A[], int& n) {
    int res = A[1]; // 记录堆顶元素
    A[1] = A[n]; // 把堆顶元素换到最后
    n--; // 调整大小，此时原来的最后一位虽然有值但不会再用了
    int p = 1, t;
    while (p * 2 <= n) { // 调整
        if (p * 2 + 1 > n || A[p * 2] <= A[p * 2 + 1]) { // 找到左右两个孩子中的较小者
            t = p * 2;
        } else {
            t = p * 2 + 1;
        }
        if (A[p] > A[t]) { // 如果不满足堆的性质就交换
            swap(A[p], A[t]);
            p = t;
        } else { // 否则就调整完成了
            break;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优先队列

先需要了解队列
如果只想要浅显的了解一下优先队列请点击这里
我们在之前的课程中已经接触了队列这个数据结构。利用队列先进先出的性质，可以解决很多实际问题，但对于一些特殊的情况，队列是无法解决的。
例如在医院里，重症急诊患者肯定不能像普通患者那样依次排队就诊。这时候，我们就需要一种新的数据结构——优先队列，先访问优先级高的元素。

在队列中，元素从队尾进入，从队首删除。
相比队列，优先队列里的元素增加了优先级的属性，优先级高的元素先被删除。优先队列内部是用堆实现的。
优先队列的使用和队列基本上没有区别，下面给出 C++ 实例代码。

#include <queue>
#include <iostream>
using namespace std;
int main() {
    priority_queue<int> q; // 声明一个装 int 类型数据的优先队列
    q.push(1); // 入队
    q.push(2);
    q.push(3);
    while (!q.empty()) { // 判断队列是否为空
        cout << q.top() << endl; // 访问队列首元素
        q.pop(); // 出队
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出为3 2 1
优先队列会默认把优先级大的数据放在前面，因为它内部是一个大根堆，如果向把小的数据放在前面应该这么写：
prioritity_queue<int,vector<int>,greater<int> > q
(默认的优先队列，即大根堆是这么写的：priority_queue<int,vector<int>,less<int> > q）
为了避免> >被计算机当作右移符号，中间最好还是要打空格
这个写法的含义是，这个优先队列里装int，这个优先队列内部用vector存储，比较方式是greater，在使用优先队列的时候用greater的方式比较会把较小的元素放在队首。
英文好的人可能会说：不对啊，greater是更大的意思，但其实这样是因为优先队列的排序机制是反着的，在后续的结构体优先队列中的优先级设定也应该是反的

优先队列，可以存放数值，也可以存放其它数据类型（包括自定义数据类型）。该容器支持查询优先级最高的元素这一操作，而优先级的高低是可以自行定义的。
在 C++ 中我们可以通过重载小于运算符operator <来实现。
比如，下面这个是定义运算值小的，优先级别高

struct node {
    int dist, loc;
    node() { }
    bool operator < (const node & a) const {
        return dist > a.dist;
    }
};

priority_queue <node> Q;
1
2
3
4
5
6
7
8
9

上述代码起到优先级重载的作用，我们仍然可以进行top、pop等便捷的操作。