堆 (数据结构)

最后更新于

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

过程如下:

  1. 先找到当前新节点的父节点,如果不满足堆的大小关系,交换
  2. 继续执行 1 直到整个树都满足堆的性质

这个过程最多执行 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

过程如下:

  1. 先随便取一个叶子当作根
  2. 找到当前新根的子节点,调整位置直到整个树符合堆的性质

这个过程最多执行 O(log n) 次。

堆排序

让我看看,删除根节点的复杂度是 O(log n),且根节点总是最值,那么重复执行 n 次我们就获得了堆排!其复杂度显然为 O(n log n)。

从杂乱的数据建堆

如果直接跑插入算法,其总复杂度为 O(n log n);不过我们有更聪明的做法:直接对原数据做调整使其符合堆的性质。当使用数组实现二叉树时,原数据也在数组里,可以直接看做是树:

583
  5
 / \
8   3
7583
    7
   / \
  5   8
 /
3

注意到,每次往数组前面多取一个元素时,对应的二叉树等价于把新的元素插入到了根节点,其他节点往后顺延,这偶尔会破坏树的性质,但不多。

上一个根节点发生改变的地方是删除根的操作,我们可以利用相同的思路,不断从根往下调整节点使其符合堆的性质。这种算法的总复杂度是 O(n)。

堆合并

类似的,我们可以把两个堆先合并成一个看似杂乱的数据(例如,数组可以直接 concat,树的话可以先构造一个新的根,把两个树都放到这个根下,然后参考上面删除根的做法),接着使用建堆的算法就可以在总复杂度 O(n) 的情况下完成合并。

O(1) 堆合并

如果要达到 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

他的复杂度是第二层的长度。