堆：一个父节点一定不大于(不小于)子节点的树形数据结构。

支持 插入元素，删除元素，查询最大/最小的元素。

前两者操作复杂度为 \(O(\log n)\) ，查询操作复杂度为 \(O(1)\) 。

1. 优先队列（STL）

大根堆：priority_queue heap;

小根堆：priority_queue <int , vector , greater > heap;

二元组优先队列直接用 pair 即可，默认先第一关键字后第二关键字。

2. 堆Heap（手写堆）

这个原来我是不想学的，结果扫了眼 Heap 的实现原理发现...这个数据结构非常简单，基本知道三个要点即可简单实现：（以小根堆为例）

(1). 存储方式和线段树一致。

(k << 1) 为左儿子，(k << 1 | 1) 为右儿子，(k >> 1)为父节点。

(2). 插入操作就是在数组尾部插入一个数，然后递归地上传。

如果 heap[k] < heap[k >> 1] 就上传。否则停止上传操作。

(3). 删除操作就是删除 heap[1] ，然后拿 heap[siz] 代替 heap[1] 之后将其递归地下传。

如果 heap[k] > min(heap[k << 1] , heap[k << 1 | 1]) 就下传，否则停止下传操作。

Code

3. 启发式合并

每次合并从 \(size\) 小的合并到 \(size\) 大的里面，并查集维护哪些在一个集合中以及每个集合 \(size\) 的大小。复杂度 \(O(n \log^2 n)\) 。