普通的数据结构课程中不会提到堆,但它也是一种生活中常见的工具,常用来实现优先队列等。当使用二叉树实现时,他有着查询顶点 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
他的复杂度是第二层的长度。