数据结构：树与堆

Python 标准库 没有 红黑树或 B 树容器。树家族在 CPython 里的生产入口只有两条：

1. 堆（heap）：heapq，数组下的完全二叉树，只保证堆序。
2. 有序数组 + 折半：bisect，用连续 list 换 (O(\log n)) 查找、(O(n)) 插入。

手写 二叉搜索树（Binary Search Tree，BST）、字典树（Trie）、并查集（Union-Find） 是算法题与特定场景，不是默认容器。

段末注释：堆序只约束「父优于子」，不保证中序有序；BST 才保证左 < 根 < 右。两者都是树，操作契约不同。

---

1. 选型

你要的操作	用这个	复杂度
反复取最小 / 最大	heapq	入堆出堆 (O(\log n))，看堆顶 (O(1))
有序序列里找插入点	bisect	查找 (O(\log n))
偶尔插入且 (n) 不大	list + bisect.insort	插入 (O(n))
频繁插入且保持键有序	第三方 sortedcontainers	期望 (O(\log n))
前缀匹配	嵌套 dict 当 Trie	与键长成正比
连通性 / 分组合并	并查集	近乎 (O(1))（反 Ackermann）

不要为「有一个 TreeMap」在 Python 里手写红黑树。那是 C++ std::map 的事。

---

2. 堆：heapq 是最小堆

底层就是普通 list：下标 (i) 的孩子是 (2i+1)、(2i+2)。heap[0] 永远是当前最小。

import heapq

def merge_k(lists):
    """k 路有序表归并。

    输入：lists，每个元素已升序。
    输出：一条升序 list。
    处理：堆里放 (值, 表号, 下标)，弹出谁就推进谁。
    """
    h, out = [], []
    for i, row in enumerate(lists):
        if row:
            heapq.heappush(h, (row[0], i, 0))
    while h:
        val, i, j = heapq.heappop(h)
        out.append(val)
        j += 1
        if j < len(lists[i]):
            heapq.heappush(h, (lists[i][j], i, j))
    return out


def top_k_max(nums, k):
    """最大的 k 个（堆里只留 k 个最小候选）。

    输入：nums 可迭代，k 正整数。
    输出：无序的 k 个最大值（要有序再 sort）。
    处理：维护规模 k 的最小堆，比堆顶大才替换。
    """
    h = []
    for x in nums:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:
            heapq.heapreplace(h, x)
    return h

API	作用
heapify(a)	原地建堆 (O(n))
heappush / heappop	入 / 出最小
heappushpop / heapreplace	组合操作，少一次调整
nlargest / nsmallest	(k \ll n) 时比全排序快
merge	多路已序迭代器归并

最大堆：压 -x，或压 (-priority, x)。只比对象时，必须保证同类可比较，或自己拆成元组，避免 TypeError。

优先级相同要稳定：压 (priority, seq, item)，seq 是单调计数器。queue.PriorityQueue 是这套东西加一把锁。

---

3. 有序数组：bisect

import bisect

def rank_of(sorted_xs, x):
    """x 在升序数组里应插入的位置（左边界）。

    输入：sorted_xs 已升序，x 可比较。
    输出：下标 i，满足左侧都 < x。
    处理：bisect_left，O(log n) 次比较。
    """
    return bisect.bisect_left(sorted_xs, x)

函数	含义
bisect_left	第一个 (\ge x) 的位置
bisect_right	第一个 (> x) 的位置
insort_left / insort_right	插入并保持有序（内部仍是 list.insert，(O(n))）

(n) 到 (10^5) 且插入频繁时，insort 会慢。那时才上 sortedcontainers.SortedList。

---

4. 手写 BST / Trie / 并查集

教学与算法题用。BST 退化成链时查找变 (O(n))，生产不靠它保序。

class BSTNode:
    """二叉搜索树节点：左子 < val < 右子。"""

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def bst_insert(root, val):
    """插入值，重复值忽略。

    输入：root 为 BSTNode 或 None，val 可比较。
    输出：新根。
    处理：小的走左、大的走右，空位挂上新节点。
    """
    if root is None:
        return BSTNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    elif val > root.val:
        root.right = bst_insert(root.right, val)
    return root


def make_trie(words):
    """用嵌套 dict 建字典树。

    输入：words 字符串可迭代。
    输出：根 dict；路径上的 "$" 标记词尾。
    处理：逐字符 setdefault 下一层。
    """
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = True
    return root


class UnionFind:
    """并查集：路径压缩 + 按秩合并。

    输入：构造 n 为元素个数 0..n-1。
    find(x) → 根；union(a, b) → 是否把两组合并（原先不在一组为 True）。
    处理：父指针森林；find 时压平路径，union 时小树挂大树。
    """

    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0] * n

    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True

线段树 / 树状数组没有标准库。竞赛与区间题再手写；业务里区间统计更常见的是先排序再扫，或把数据丢进数据库 / pandas。

B / B+ 树是磁盘索引的形状，在 Python 进程里你碰到的是 SQLite / 引擎，不是一个 BPlusTree 类。

---

5. 踩坑

1. 把堆当有序数组：sorted(heap) 才有序；直接 for x in heap 不是排序遍历。
2. heappop 空堆：IndexError。先判空。
3. 元组比较：(1, "b") 能和 (1, "a") 比，但 (1, None) 在部分版本会炸。优先级元组字段要类型一致。
4. bisect 用在未排序 list：不报错，结果错。
5. BST 插入有序序列：退化成链表。要平衡去用第三方或换结构。

---

6. 自检

1. 堆和 BST 哪个能 (O(1)) 看最值？哪个能中序得到有序序列？
2. heapq 只有最小堆，最大堆怎么做？
3. bisect.insort 查找很快，插入为什么仍可能慢？
4. 并查集的 find 为什么要路径压缩？

---

7. 社区口径与风险

heapq、bisect 是标准库首选。有序映射 / 有序表的社区方案是 sortedcontainers（SortedList / SortedDict，内部是分块 + 折半）；风险是多一个依赖，以及它不是红黑树，极端模式的常数与 C++ std::map 不同。不要为对标 Java TreeMap 自己写一套旋转。