普通的数据结构课程中不会提到堆，但它也是一种生活中常见的工具，常用来实现优先队列等。当使用二叉树实现时，他有着查询顶点 O(1)，插入 O(log n) 的优秀性质，下面就来看看。
堆需要满足根节点和子节点始终保证相同的比较关系，比如根节点始终是最小的节点。已知这个条件后，我们可以很轻松地推导出实现：
我们尝试把新节点直接塞进某个树的叶子位置，此时可能会有一个地方满足不了堆的需求：
5
/ \ <- 试试交换这条边上的两个节点
8 1(新节点)
1
/ \ 完成！
8 5
嗯，如果有很多层呢？
5
/ \
8 9
/ \ \ <- 总之先交换他们看看
10 11 1(新节点)
5
/ \ <- 也许再交换一下他们？
8 1
/ \ \
10 11 9
1
/ \
8 5 完成！
/ \ \
10 11 9
过程如下：
这个过程最多执行 O(log n) 次。
为了删除根，需要找到一个新的根来代替他，不妨直接取一片叶子：
根被我拿走啦
/ \
5 6
/ \ / \
7 8 9 10 <- 直接把它放到根部如何
10 -.
/ \ > 这里不满足性质，交换 10-5 使其满足
5 6 -'
/ \ /
7 8 9
5
/ \
10 6 -.
/ \ / > 继续交换 10-7 使其满足性质
7 8 9 -'
5
/ \
7 6 完成！
/ \ /
10 8 9
过程如下：
这个过程最多执行 O(log n) 次。
让我看看，删除根节点的复杂度是 O(log n)，且根节点总是最值，那么重复执行 n 次我们就获得了堆排！其复杂度显然为 O(n log n)。
如果直接跑插入算法，其总复杂度为 O(n log n)；不过我们有更聪明的做法：直接对原数据做调整使其符合堆的性质。当使用数组实现二叉树时，原数据也在数组里，可以直接看做是树：
| 5 | 8 | 3 |
5
/ \
8 3
| 7 | 5 | 8 | 3 |
7
/ \
5 8
/
3
注意到，每次往数组前面多取一个元素时，对应的二叉树等价于把新的元素插入到了根节点，其他节点往后顺延，这偶尔会破坏树的性质，但不多。
上一个根节点发生改变的地方是删除根的操作，我们可以利用相同的思路，不断从根往下调整节点使其符合堆的性质。这种算法的总复杂度是 O(n)。
类似的，我们可以把两个堆先合并成一个看似杂乱的数据（例如，数组可以直接 concat，树的话可以先构造一个新的根，把两个树都放到这个根下，然后参考上面删除根的做法），接着使用建堆的算法就可以在总复杂度 O(n) 的情况下完成合并。
如果要达到 O(1) 的合并算法，我们需要稍微改动一下这个树的形态：
3
/ \ 这是一般的二叉树
8 5
3
/ 考虑每一行组成单链表，此时父节点只需要存储子链表的首节点即可
8---5
接着考虑两棵树合并的操作，需要有一棵树的根节点成为另一棵的子链表的首节点，
1 4
/ + / =
2---3 5---6
1
/
4--2--3 注意看，每个节点所在的子树仍然符合堆的性质
/
5---6
这样就做到了 O(1) 合并，但是这种形态的堆怎么实现插入和删除呢？
我们直接把新节点和根节点合并，看看会发生什么，
1 1
/ + 4 = /
2---3 4--2--3
1 0
/ /
2---3 + 0 = 1
/
2---3
好像没有问题！甚至插入的复杂度还是 O(1)，不过由于不是完全二叉树，这个玩意儿势必在某些地方要表现出比较菜的性能…
去掉根之后，整个堆的第二层是一个单链表，那我直接对它进行一个 reduce merge：
根被我拿走啦
/
1--X--4 这一行是个单链表，直接切断之后合并成一个新堆
/
2--3
1 1
/ + 4 = /
2--3 4--2--3
他的复杂度是第二层的长度。