贪心算法进阶：霍夫曼编码、最小生成树

贪心算法走到这一步，已经不是简单的「选最大」或「选最小」了。说实话，霍夫曼编码和最小生成树这两个问题，是我在实际项目中真正感受到贪心「威力」的地方。它们看起来风马牛不相及——一个搞数据压缩，一个搞网络布线——但骨子里的贪心逻辑，其实是一模一样的。

我个人习惯把这类问题叫做「局部最优能推全局最优」的典型代表。你想想看，每次做选择时都挑当前最好的，最后居然能得到全局最优解，这本身就很神奇。但要注意，不是所有问题都吃这套，后面我会提到哪些场景会翻车。

霍夫曼编码：数据压缩的基石

先聊聊霍夫曼编码。我记得刚入行时，有个项目需要传输大量传感器数据，带宽有限，压缩率就是命。当时我试了好几种算法，最后发现霍夫曼编码虽然简单，但效果出奇的好。

它的核心思想其实就一句话：出现频率高的字符，用短编码；出现频率低的字符，用长编码。这就像你给公司里常联系的人存短号，不常联系的人存全号一样——整体效率就上来了。

算法步骤

  1. 统计每个字符的出现频率
  2. 把每个字符看作一个叶子节点，频率作为权重
  3. 每次取出两个权重最小的节点，合并成一个新节点
  4. 新节点的权重等于两个子节点之和
  5. 重复步骤3-4，直到只剩一个节点（根节点）
  6. 从根到叶子的路径，左分支为0，右分支为1，得到编码

关键点：霍夫曼编码是前缀编码，任何一个字符的编码都不是另一个字符编码的前缀。这意味着解码时不会产生歧义。

代码实现

import heapq
from collections import Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    # 统计频率
    freq = Counter(text)
    
    # 构建最小堆
    heap = [HuffmanNode(char, f) for char, f in freq.items()]
    heapq.heapify(heap)
    
    # 贪心合并
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)
    
    return heap[0]

def generate_codes(node, prefix="", code_map=None):
    if code_map is None:
        code_map = {}
    if node.char is not None:
        code_map[node.char] = prefix
    else:
        generate_codes(node.left, prefix + "0", code_map)
        generate_codes(node.right, prefix + "1", code_map)
    return code_map

# 示例
text = "hello world"
tree = build_huffman_tree(text)
codes = generate_codes(tree)
print(codes)
# 输出类似：{'h': '000', 'e': '001', 'l': '01', 'o': '10', ' ': '110', 'w': '1110', 'r': '1111', 'd': '11110'}

避坑指南：我曾经在实现时忘记处理只有一个字符的情况，结果堆里只剩一个节点时循环条件没处理好，直接报错。记住，当文本中只有一种字符时，编码就是单个比特0，不需要构建树。

最小生成树：Prim算法

最小生成树（MST）的问题，说白了就是：给你一堆节点和带权重的边，怎么用最少的成本把所有节点连起来？我在做网络拓扑规划时遇到过类似问题——要在多个机房之间铺设光纤，每段成本不同，怎么布线最省钱？

Prim算法的思路很直观：从一个节点出发，每次找离当前「已选集合」最近的节点加进来。这就像你建一个朋友圈，先拉一个人进来，然后每次拉一个跟圈子里任何人关系最近的人。

算法步骤

  1. 任选一个起始节点，加入已选集合
  2. 找到连接已选集合和未选集合的最小权值边
  3. 把这条边对应的未选节点加入已选集合
  4. 重复步骤2-3，直到所有节点都在已选集合中

代码实现

import heapq

def prim_mst(graph, start=0):
    """
    graph: 邻接矩阵，graph[i][j] = 权重，不连通为inf
    start: 起始节点
    返回: (总权重, 边列表)
    """
    n = len(graph)
    visited = [False] * n
    # (权重, 当前节点, 父节点)
    heap = [(0, start, -1)]
    total_weight = 0
    edges = []
    
    while heap:
        weight, node, parent = heapq.heappop(heap)
        if visited[node]:
            continue
        visited[node] = True
        total_weight += weight
        if parent != -1:
            edges.append((parent, node, weight))
        
        for neighbor in range(n):
            if not visited[neighbor] and graph[node][neighbor] != float('inf'):
                heapq.heappush(heap, (graph[node][neighbor], neighbor, node))
    
    return total_weight, edges

# 示例
graph = [
    [0, 2, 3, float('inf')],
    [2, 0, 1, 4],
    [3, 1, 0, 5],
    [float('inf'), 4, 5, 0]
]
total, edges = prim_mst(graph)
print(f"总权重: {total}")
print(f"边: {edges}")
# 输出: 总权重: 7, 边: [(0, 1, 2), (1, 2, 1), (1, 3, 4)]

注意：Prim算法适用于稠密图，因为它的时间复杂度是O(V²)（用堆优化后是O(E log V)）。如果图很稀疏，Kruskal算法通常更快。

最小生成树：Kruskal算法

Kruskal算法和Prim的思路完全不同。它不看节点，只看边——把所有边按权重从小到大排序，然后一条一条加进来，只要不形成环就保留。这就像你手里有一堆材料，每次挑最便宜的那个用，但前提是不能让已有的结构变成闭环。

我更喜欢Kruskal的原因在于，它天然适合处理边集数据。比如你手头只有各段光纤的报价单，根本不需要知道机房之间的完整拓扑，直接排序加边就行。

算法步骤

  1. 把所有边按权重从小到大排序
  2. 初始化并查集，每个节点独立成集
  3. 从小到大遍历每条边
  4. 如果边的两个端点不在同一个集合中，加入这条边，合并两个集合
  5. 重复步骤3-4，直到加入n-1条边

代码实现

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

def kruskal_mst(n, edges):
    """
    n: 节点数量
    edges: 边列表，每个元素为 (权重, u, v)
    返回: (总权重, 边列表)
    """
    edges.sort()  # 按权重排序
    uf = UnionFind(n)
    total_weight = 0
    mst_edges = []
    
    for weight, u, v in edges:
        if uf.union(u, v):
            total_weight += weight
            mst_edges.append((u, v, weight))
            if len(mst_edges) == n - 1:
                break
    
    return total_weight, mst_edges

# 示例
n = 4
edges = [
    (2, 0, 1),
    (3, 0, 2),
    (1, 1, 2),
    (4, 1, 3),
    (5, 2, 3)
]
total, mst_edges = kruskal_mst(n, edges)
print(f"总权重: {total}")
print(f"边: {mst_edges}")
# 输出: 总权重: 7, 边: [(1, 2, 1), (0, 1, 2), (1, 3, 4)]

经验之谈：我曾经在项目中用Kruskal处理过10万个节点的图，排序是瓶颈。如果边数特别多，可以考虑用计数排序或桶排序来优化，但大多数情况下Python内置的Timsort已经够用了。

三种算法的对比

算法 核心思想 时间复杂度 适用场景
霍夫曼编码 频率高的短编码 O(n log n) 数据压缩、文件编码
Prim算法 从节点出发，找最近邻 O(V²) 或 O(E log V) 稠密图的最小生成树
Kruskal算法 从边出发，避免成环 O(E log E) 稀疏图的最小生成树

你可能会问：为什么这些贪心算法能保证全局最优？其实关键在于它们都满足「最优子结构」和「贪心选择性质」。说白了，就是局部最优的选择不会影响后续选择，而且每一步的最优解拼起来就是全局最优。但这种情况在现实中很少见，所以贪心算法才显得珍贵。

核心总结：霍夫曼编码、Prim和Kruskal，这三个算法是贪心思想在树形结构上的完美体现。它们教会我们一件事——有时候，目光短浅一点反而能走得更远。

贪心算法进阶知识体系 贪心算法进阶 霍夫曼编码 Prim算法 Kruskal算法 频率统计 最小堆合并 前缀编码 邻接矩阵 优先队列 已选集合 边排序 并查集 避免成环

嗯，到这里三种算法就讲完了。说实话，每次讲这部分我都会想起当年做压缩工具时，用霍夫曼编码把日志文件从50MB压到12MB的成就感。算法这东西，学的时候觉得抽象，用起来才知道有多香。

专注资料整理

← 上一章 📖 返回目录 下一章 →