algo05 堆、并查集与跳跃表 — exercise.py 练习指南

Download exercise.py

练习目标

通过四个任务掌握堆、并查集和跳跃表的核心操作。

任务清单

任务1：实现最大堆

最大堆与最小堆的唯一区别是 _sift_up 和 _sift_down 中的比较方向反转。push 时大于父节点就交换，pop 时与较大的子节点交换。

任务2：补全并查集

find 路径压缩：if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])

union 按秩合并：总是将秩（树高上界）较小的根挂到秩较大的根下。秩相等时，选一个作为新的根，秩+1。

任务3：连通分量计数

将每条边的两端点 union，所有操作结束后，set_count 就是连通分量数量。

任务4（Bonus）：跳跃表 search 和 insert

search：从最高层向下搜索，每层尽可能前进直到遇到大于等于目标的值。 insert：记录每层前驱，随机生成层数后插入。

验证

bash

cd algo05_heap_unionfind_skiplist/code
python exercise.py

完整代码

# -*- coding: utf-8 -*-
"""
===============================================================================
algo05_heap_unionfind_skiplist/code/exercise.py — 堆、并查集与跳跃表练习
===============================================================================
练习目标：
  1. 实现最大堆（MaxHeap）的 push/pop
  2. 实现并查集的 find（路径压缩）和 union（按秩合并）
  3. 使用并查集求解连通分量数量
  4. 完成跳跃表的部分实现

运行方式：python exercise.py
===============================================================================
"""

import random


# ============================================================================
# 任务 1：实现最大堆
# ============================================================================

class MaxHeap:
    """最大堆 —— 根节点是最大值"""

    def __init__(self):
        self._data = []

    # TODO: 实现 push
    def push(self, item):
        self._data.append(item)
        self._sift_up(len(self._data) - 1)

    # TODO: 实现 pop
    def pop(self):
        if not self._data:
            raise IndexError('堆空')
        if len(self._data) == 1:
            return self._data.pop()
        root = self._data[0]
        self._data[0] = self._data.pop()
        self._sift_down(0)
        return root

    def _sift_up(self, idx):
        """上浮：大于父节点时交换"""
        parent = (idx - 1) // 2
        while idx > 0 and self._data[idx] > self._data[parent]:
            self._data[idx], self._data[parent] = self._data[parent], self._data[idx]
            idx = parent
            parent = (idx - 1) // 2

    def _sift_down(self, idx):
        """下沉：与较大的子节点交换"""
        n = len(self._data)
        while True:
            largest = idx
            left = 2 * idx + 1
            right = 2 * idx + 2
            if left < n and self._data[left] > self._data[largest]:
                largest = left
            if right < n and self._data[right] > self._data[largest]:
                largest = right
            if largest == idx:
                break
            self._data[idx], self._data[largest] = self._data[largest], self._data[idx]
            idx = largest

    def __repr__(self):
        return f'MaxHeap({self._data})'


# ============================================================================
# 任务 2：补全并查集
# ============================================================================

class UnionFind:
    """并查集（待补全）"""

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.set_count = n

    # TODO: 实现 find（带路径压缩）
    def find(self, x):
        # TODO: 如果 parent[x] != x，递归查找并路径压缩
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    # TODO: 实现 union（按秩合并）
    def union(self, x, y):
        # TODO: 找到 x, y 的根，按秩合并
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        self.set_count -= 1
        return True


# ============================================================================
# 任务 3：使用并查集统计连通分量
# ============================================================================

def count_connected_components(n, edges):
    """给定 n 个节点和边列表，返回连通分量的数量

    参数:
      n: 节点数量 (0 到 n-1)
      edges: [(u, v), ...] 无向边列表

    返回:
      连通分量的数量
    """
    # TODO: 你的代码
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.set_count


# ============================================================================
# 任务 4（Bonus）：补全跳跃表的 search 和 insert
# ============================================================================

class SkipNode:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)


class SkipList:
    MAX_LEVEL = 8
    P = 0.5

    def __init__(self):
        self.head = SkipNode(float('-inf'), self.MAX_LEVEL)
        self.level = 0
        self._size = 0

    def _random_level(self):
        level = 0
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level

    # TODO: 实现 search
    def search(self, target):
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].value < target:
                cur = cur.forward[i]
        cur = cur.forward[0]
        return cur is not None and cur.value == target

    # TODO: 实现 insert
    def insert(self, value):
        update = [None] * (self.MAX_LEVEL + 1)
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur

        new_level = self._random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.head
            self.level = new_level

        new_node = SkipNode(value, new_level)
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
        self._size += 1

    def to_list(self):
        result = []
        cur = self.head.forward[0]
        while cur:
            result.append(cur.value)
            cur = cur.forward[0]
        return result


# ============================================================================
# 主函数
# ============================================================================

def main():
    print('=' * 60)
    print('  堆、并查集与跳跃表 — 练习程序')
    print('=' * 60)

    # 测试任务 1
    print('\n--- 任务 1：最大堆 ---')
    mh = MaxHeap()
    for x in [3, 1, 4, 1, 5, 9, 2]:
        mh.push(x)
    print(f'push 后: {mh}')
    sorted_desc = [mh.pop() for _ in range(len(mh._data))]
    print(f'弹出顺序（降序）: {sorted_desc}')
    assert sorted_desc == sorted([3, 1, 4, 1, 5, 9, 2], reverse=True)
    print('✅ 任务 1 通过！')

    # 测试任务 2
    print('\n--- 任务 2：并查集 ---')
    uf = UnionFind(6)
    uf.union(0, 1); uf.union(1, 2)
    uf.union(3, 4)
    print(f'find(0)={uf.find(0)}, find(2)={uf.find(2)} (应相等)')
    print(f'find(3)={uf.find(3)}, find(4)={uf.find(4)} (应相等)')
    print(f'find(0)!={uf.find(3)} (应不相等)')
    assert uf.find(0) == uf.find(2)
    assert uf.find(0) != uf.find(3)
    print('✅ 任务 2 通过！')

    # 测试任务 3
    print('\n--- 任务 3：连通分量 ---')
    edges = [(0, 1), (1, 2), (3, 4)]
    count = count_connected_components(6, edges)
    print(f'n=6, edges={edges} → 连通分量数 = {count}')
    assert count == 3  # {0,1,2}, {3,4}, {5}
    print('✅ 任务 3 通过！')

    # 测试任务 4
    print('\n--- 任务 4：跳跃表 ---')
    sl = SkipList()
    for v in [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]:
        sl.insert(v)
    print(f'插入后: {sl.to_list()}')
    assert sl.search(4) and sl.search(9) and not sl.search(7)
    print('✅ 任务 4 通过！')

    print('\n🎉 所有练习已完成！')


if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247

algo05 堆、并查集与跳跃表 — exercise.py 练习指南 ​

练习目标 ​

任务清单 ​

任务1：实现最大堆 ​

任务2：补全并查集 ​

任务3：连通分量计数 ​

任务4（Bonus）：跳跃表 search 和 insert ​

验证 ​

完整代码 ​