二叉堆：一种隐式二叉树

堆概述

这里我们讨论两种非常有用的优先队列（priority Queue）数据结构的实现方式。这两种结构都是称为堆（heap）的特殊二叉树，意为“杂乱无章的一堆”。这与二叉搜索树形成对比，后者可以看作是一个高度有序的堆。

第一种堆的实现使用数组来模拟一棵完全二叉树。这种实现非常高效，是目前已知最快的排序算法之一——堆排序（heapsort）的基础。第二种实现基于更灵活的二叉树结构，支持一个 meld(h) 操作，允许优先队列吸收另一个优先队列 h 中的所有元素。

BinaryHeap：隐式二叉树

我们对（优先）队列的第一个实现基于一种已有四百多年历史的技术。艾茨宁方法（Eytzinger’s method）通过按广度优先顺序排列树的节点，将一棵完全二叉树表示为数组。这样，根节点存储在位置 $0$，根的左孩子存储在位置 $1$，右孩子在位置 $2$，根的左孩子的左孩子在位置 $3$，依此类推。

如果对足够大的树应用艾茨宁方法，会显现出一些规律：位于索引 i 的节点的左孩子在索引 left(i) = 2i + 1，右孩子在索引 right(i) = 2i + 2，而其父节点在索引 parent(i) = (i − 1) // 2。

1def left(i):
2    return 2*i + 1
3
4def right(i):
5    return 2*(i+1)
6
7def parent(i):
8    return (i-1)//2

BinaryHeap 使用这一技术，隐式地表示一棵完全二叉树，其中元素满足堆序性质：任意位置 i 存储的值不小于其父节点 parent(i) 处的值，除了根节点（i = 0）。因此，优先队列中的最小值必然存储在位置 $0$（即根节点）。

在 BinaryHeap 中，n 个元素存储在一个数组 a 中：

1class BinaryHeap(BaseSet):
2    def __init__(self, iterable=[], a=None):
3        if a: 
4            self._make_heap(a)
5        else:
6            self._initialize()
7            self.add_all(iterable)
8
9    def _initialize(self):
10        self.a = new_array(1)
11        self.n = 0

add() 操作

实现 add(x) 操作相对简单。如同所有基于数组的结构一样，我们首先检查数组 a 是否已满（通过判断 a.length == n），如果是，则扩大数组。接着将 x 放入 a[n]，并递增 n。此时，只需确保维持堆的性质即可。我们通过不断将 x 与其父节点交换，直到 x 不再小于其父节点为止。

实现 add() 方法如下：

1class BinaryHeap(BaseSet):
2    def __init__(self, iterable=[], a=None):
3        if a: 
4            self._make_heap(a)
5        else:
6            self._initialize()
7            self.add_all(iterable)
8
9    def add(self, x):
10        if len(self.a) < self.n+1:
11            self.resize()
12        self.a[self.n] = x
13        self.n += 1
14        self.bubble_up(self.n-1)
15        return True
16
17    def bubble_up(self, i):
18        p = parent(i)
19        while i > 0 and self.a[i] < self.a[p]:
20            self.a[i], self.a[p] = self.a[p], self.a[i]
21            i = p
22            p = parent(i)

remove() 操作

实现 remove() 操作（移除最小值）稍复杂一些。我们知道最小值位于根节点，但移除后需要替换它，并保证仍满足堆的性质。

最简便的方法是用 a[n - 1] 替换根节点，删除该值并递减 n。但此时新根可能不再是最小值，因此需要向下调整。我们通过不断将该节点与其两个子节点比较。如果它是三者中最小的，则停止；否则，将其与两个子节点中较小的一个交换，并继续向下进行。

实现 remove() 方法如下：

1class BinaryHeap(BaseSet):
2    def __init__(self, iterable=[], a=None):
3        if a: 
4            self._make_heap(a)
5        else:
6            self._initialize()
7            self.add_all(iterable)
8
9    def remove(self):
10        x = self.a[0]
11        self.a[0] = self.a[self.n-1]
12        self.n -= 1
13        self.trickle_down(0)
14        if 3*self.n < len(self.a):
15            self.resize()
16        return x
17
18    def trickle_down(self, i):
19        while i >= 0:
20            j = -1
21            r = right(i)
22            if r < self.n and self.a[r] < self.a[i]:
23                l = left(i)
24                if self.a[l] < self.a[r]:
25                    j = l
26                else:
27                    j = r
28            else:
29                l = left(i)
30                if l < self.n and self.a[l] < self.a[i]:
31                    j = l
32            if j >= 0:
33                self.a[j], self.a[i] = self.a[i], self.a[j]
34            i = j

与其它基于数组的结构一样，我们忽略 resize() 调用所花费的时间，因为可以通过摊销分析来处理。add(x) 和 remove() 的运行时间取决于（隐式）二叉树的高度。幸运的是，这是一棵完全二叉树：除最后一层外，每一层都包含最大数量的节点。因此，若树的高度为 h，则节点数至少为 $2^h$。换句话说：

$$n \geq 2^h$$

对两边取对数得：

$$h \leq \log n$$

因此，add(x) 和 remove() 操作的时间复杂度均为 $O(\log n)$。

总结

以下定理总结了 BinaryHeap 的性能表现：

定理：BinaryHeap 实现了（优先）队列接口。忽略 resize() 调用的代价，BinaryHeap 在每次操作中支持 add(x) 与 remove()，时间复杂度为 $O(\log n)$。

此外，从空的 BinaryHeap 开始，任意长度为 $m$ 的 add(x) 和 remove() 操作序列，所有 resize() 调用的总耗时为 $O(m)$。

1import random
2import time
3from utils import new_array
4from base import BaseSet
5
6# 左子节点函数
7def left(i):
8    return 2*i + 1
9
10# 右子节点函数
11def right(i):
12    return 2*(i+1)
13
14# 父节点函数
15def parent(i):
16    return (i-1)//2
17
18# 主类
19class BinaryHeap(BaseSet):
20    def __init__(self, iterable=[], a=None):
21        if a: 
22            self._make_heap(a)
23        else:
24            self._initialize()
25            self.add_all(iterable)
26
27    # 构建堆
28    def _make_heap(self, a):
29        self.a = a
30        self.n = len(a)
31        for i in range(self.n//2-1, -1, -1):
32            self.trickle_down(i)
33
34    # 初始化
35    def _initialize(self):
36        self.a = new_array(1)
37        self.n = 0
38
39    clear = _initialize
40
41    # 调整数组大小
42    def resize(self):
43        b = new_array(max(2*self.n, 1))
44        for i in range(self.n):
45            b[i] = self.a[i]
46        self.a = b
47
48    # 添加元素
49    def add(self, x):
50        if len(self.a) < self.n+1:
51            self.resize()
52        self.a[self.n] = x
53        self.n += 1
54        self.bubble_up(self.n-1)
55        return True
56
57    # 向上调整
58    def bubble_up(self, i):
59        p = parent(i)
60        while i > 0 and self.a[i] < self.a[p]:
61            self.a[i], self.a[p] = self.a[p], self.a[i]
62            i = p
63            p = parent(i)
64
65    # 移除最小元素
66    def remove(self):
67        x = self.a[0]
68        self.a[0] = self.a[self.n-1]
69        self.n -= 1
70        self.trickle_down(0)
71        if 3*self.n < len(self.a):
72            self.resize()
73        return x
74
75    # 向下调整
76    def trickle_down(self, i):
77        while i >= 0:
78            j = -1
79            r = right(i)
80            if r < self.n and self.a[r] < self.a[i]:
81                l = left(i)
82                if self.a[l] < self.a[r]:
83                    j = l
84                else:
85                    j = r
86            else:
87                l = left(i)
88                if l < self.n and self.a[l] < self.a[i]:
89                    j = l
90            if j >= 0:
91                self.a[j], self.a[i] = self.a[i], self.a[j]
92            i = j
93
94    # 查找最小值
95    def find_min(self):
96        if self.n == 0: raise IndexError()
97        return self.a[0]
98
99    # 迭代器
100    def __iter__(self):
101        for i in range(self.n):
102            yield self.a[i]
103
104if __name__ == "__main__":
105    # 创建对象
106    h = BinaryHeap()
107    # 随机数生成器
108    r = random.Random()
109    # 元素数量
110    n = 20
111    # 添加数值
112    print("添加数值:")
113    for i in range(n):
114        h.add(r.randint(0, 2500))
115    print(list(h))
116    # 移除数值
117    print("移除数值:")
118    while h:
119        print(h.remove(), end=", ")
120    print()
121    # 随机数组
122    print("随机数组:")
123    a = [r.randint(0, 2500) for i in range(n)]
124    a = sorted(a)
125    print(", ".join(str(x) for x in a))
126    n = 1000
127    print(f"执行 {n} 次添加...")
128    start = time.time()
129    for i in range(n):
130        h.add(r.randint(0, 2500))
131    stop = time.time()
132    elapsed = stop - start
133    print(f"({elapsed:.6f}s [{int(n/elapsed)} 次/秒])")
134
135    n *= 10
136    print(f"执行 {n} 次添加/移除...")
137    start = time.time()
138    for i in range(n):
139        if r.random() < 0.5:
140            h.add(r.randint(0, 2500))
141        else:
142            h.remove()
143    stop = time.time()
144    elapsed = stop - start
145    print(f"({elapsed:.6f}s [{int(n/elapsed)} 次/秒])")

说明

让我们从 main() 函数开始解释：

• 第93行：创建一个新的二叉堆实例 h，用于存储整数。
• 第95行：创建一个 Random 对象实例 r，用于生成随机数。
• 第100–101行：循环向堆中添加 n 个随机值，使用 add() 方法。
• 第105–106行：循环移除并打印堆中所有值，使用 remove() 方法。
• 第110行：创建一个长度为 n 的整数数组。
• 第115行：启动计时器，测量接下来操作的耗时。
• 第118行：停止计时器。
• 第119行：计算耗时（单位：秒）。
• 第120行：输出耗时及每秒操作次数。
• 第122–132行：执行 n 次添加与移除操作，并测量总耗时。