第5章：贪心的诱惑（局部最优）

:::info
兔狲教授的亲切开场
在探索了彻底搜索与智能搜索之后，我们面对一个新的问题：如何做连续的决策？ 当我们面对一系列选择时，应该步步为营还是放眼全局？今天，我们探索贪心的智慧与局限。
:::

核心议题：连续决策的策略是什么？

康乐园的午后，珠江的微风吹进黑石屋书房，带着夏初的温热。窗外的榕树新叶已经变得深绿，知了开始断断续续地鸣叫。兔狲教授正在整理茶具，准备泡一壶新的凤凰单丛。

小小猪从钱包里掏出几枚硬币，在桌上摆弄着。"教授，如果我要付8块钱，有1元、3元、5元的硬币，怎么用最少的硬币凑出来？"

小海豹放下手中的《博弈论导论》，"这个问题很有意思。如果每次都选最大面额，5+1+1+1=8，用了4个硬币。但3+3+1+1也用了4个硬币，3+5也是8元，只要2个硬币！"

兔狲教授微笑道："你们提出了一个很好的问题。当我们面对一系列决策时——无论是凑零钱、安排活动，还是规划路线——应该采用什么策略？"

小小猪不假思索，"每次选最大的硬币呗！这样用的硬币最少！"

"这就是贪心算法的思想，"兔狲教授点头，"在每一步都做出当前看起来最好的选择。但你们的例子已经显示了问题：有时候，局部最优并不导向全局最优。"

小海豹思考片刻，"所以贪心算法是短视的？只看到眼前利益，不考虑长远后果？"

"可以这么说，"兔狲教授说，"但今天我们要探索的核心议题是：连续决策的策略是什么？ 更具体地说：局部最优的选择何时能导向全局最优？"

他走到白板前，写下两个概念：

局部最优 —— 全局最优

"贪心算法的核心假设是，"兔狲教授解释，"一系列局部最优选择能导向全局最优解。但这个假设并不总是成立。今天我们要探索：它何时成立？为何成立？何时失败？为何失败？"

贪心算法的形式：选择与证明

"让我们先形式化贪心算法，"兔狲教授在白板上写出一般框架：

def greedyAlgorithm(problem):
    solution = emptySet()
    while problem not solved:
        # 选择当前最优的候选
        candidate = selectBestCandidate(problem.candidates)
        # 检查候选是否可行（满足约束）
        if feasible(solution + candidate):
            solution.add(candidate)
            problem.update(candidate)  # 更新问题状态
    return solution
​

"贪心算法有四个关键组件，"兔狲教授解释：

1. 候选集：每一步可供选择的选项
2. 选择函数：从候选集中选择"最好"的选项
3. 可行性检查：检查选择是否满足约束
4. 问题更新：选择后更新问题状态

小小猪问："'最好'怎么定义？不同的选择函数会导致不同的结果吧？"

"正是，"兔狲教授说，"选择函数的定义决定了贪心算法的行为。比如在凑零钱问题中：

• 最大面额优先：总是选不超过剩余金额的最大面额硬币
• 最小硬币优先：总是选最小的硬币
• 价值密度优先：如果硬币有不同价值（如收藏价值）

"不同的选择函数可能导致不同的结果，有的导向全局最优，有的则不然。"

活动安排问题：贪心成功案例

小海豹说："我记得活动安排问题中，贪心算法是有效的。选择结束时间最早的活动，总能得到最大兼容活动集。"

"是的，"兔狲教授在白板上写出活动安排问题：

问题：有n个活动，每个活动有开始时间sᵢ和结束时间fᵢ。选择最大数量的互不重叠活动。

贪心算法：

1. 按结束时间升序排序活动
2. 选择第一个活动（结束最早）
3. 对于后续每个活动：
   如果开始时间 ≥ 当前选中活动的结束时间：
       选择该活动
​

"这个算法的正确性需要证明，"兔狲教授说，"证明贪心选择性质：总是存在一个最优解包含结束最早的活动。"

:::info
兔狲教授的评语
活动安排问题的贪心算法成功，是因为它具有贪心选择性质和最优子结构。这两个性质是贪心算法正确性的关键。当一个问题同时具备这两个性质时，贪心策略是有效的。
:::

背包问题的失败：贪心的局限

"现在看一个贪心失败的例子，"兔狲教授说，"0-1背包问题。"

问题：有n件物品，每件物品有重量wᵢ和价值vᵢ，背包容量为W。选择物品使得总价值最大，总重量不超过W。

小小猪尝试："贪心策略：每次选价值最大的物品？"

"试试看，"兔狲教授举例，"假设背包容量W=50，物品：

1. 重量50，价值100（价值密度2）
2. 重量30，价值60（价值密度2）
3. 重量30，价值60（价值密度2）

"如果贪心选价值最大：先选物品1（价值100），但重量已满，总价值100。
"但最优解是选物品2和3：总重量60（超重？等等需要调整）……"

小海豹纠正："重量30+30=60超重了。应该：物品2重量30价值60，物品3重量30价值60，总重量60超了。"

兔狲教授重新举例："设W=50，物品：

1. 重量30，价值60（密度2）
2. 重量20，价值40（密度2）
3. 重量20，价值39（密度1.95）

"贪心选价值密度最高：先选物品1（密度2），再选物品2（密度2），总重量50，总价值100。
"但最优解是：物品2+物品3，总重量40，总价值79？不对，应该比100小……"

小小猪说："等等，这个例子中贪心好像是最优的？"

兔狲教授点头："我需要一个更好的例子。经典的反例是：W=6，物品：

1. 重量5，价值5（密度1）
2. 重量3，价值4（密度1.33）
3. 重量3，价值4（密度1.33）

"贪心选密度最高：先选物品2（价值4，剩余容量3），再选物品3（价值4，总价值8）。
"但最优解是：只选物品1（价值5）。等等，8>5，贪心更好？"

小海豹思考："W=6，物品2+3重量6价值8，物品1重量5价值5。贪心确实更好。经典反例需要物品价值不是按密度单调的……"

兔狲教授微笑："你们发现了关键。0-1背包问题的贪心策略（按价值密度排序）不是总能得到最优解，但需要精心构造反例。这也是贪心算法有趣的地方：它经常得到近似最优解，但不是绝对最优。"

:::detail
进阶科普：贪心算法的正确性证明

贪心算法的正确性通常需要证明两个性质：

1. 贪心选择性质（Greedy Choice Property）：
   存在一个最优解包含当前的贪心选择。

   证明方法：假设存在最优解不包含贪心选择，可以修改这个解，用贪心选择替换某个元素，得到另一个至少同样好的解。

2. 最优子结构（Optimal Substructure）：
   问题的最优解包含其子问题的最优解。

   证明方法：如果原问题的最优解可以分解为子问题的最优解的组合，则问题具有最优子结构。

以活动安排问题为例：

• 贪心选择性质：总是存在一个最优解包含结束最早的活动
• 最优子结构：选择活动a后，剩余问题是在a结束后开始的活动集合中选择最大兼容集

当一个问题同时具备这两个性质时，贪心算法能得到全局最优解。否则，贪心只能得到近似解。
:::

正交计算图：看见贪心的决策流

兔狲教授打开投影仪，一幅规整的计算图出现在屏幕上。

"这是贪心算法的正交计算图，"兔狲教授指着图说，"输入问题实例，经过选择函数、可行性检查、问题更新，循环直至问题解决。"

小小猪盯着图，"这个图是循环的！选择→检查→更新→再选择……像一个决策循环。"

"正是，"兔狲教授说，"贪心算法的核心是一个决策循环：在每一步，基于当前状态选择最优候选，更新状态，继续下一轮选择。这个循环结构反映了贪心算法的短视性——它只看到当前状态，不回头修改之前的选择。"

小海豹仔细观察图的层级结构，"教授，这个图的设计……选择函数、可行性检查、问题更新在同一循环层级，但每次循环后问题状态改变，候选集更新。"

"这就是贪心算法的动态性，"兔狲教授解释，"虽然算法结构是循环的，但每次循环面对的是更新的问题状态。这种状态依赖的选择是贪心算法的特点，也是其局限——一旦做出选择，就不能撤销。"

思想模型：局部最优与全局最优的张力

兔狲教授回到座位，喝了口茶。"让我们总结今天最重要的思想模型：局部最优与全局最优的张力。"

他在白板上画出对比表：

"这两种视角不是对立的，"兔狲教授解释，"而是连续谱上的两个端点。实际问题中，我们常常在两者之间寻找平衡。"

贪心策略的适用条件

小海豹问："教授，什么样的问題适合用贪心算法？"

兔狲教授在白板上列出条件：

适合贪心算法的问题通常具有：
1. **贪心选择性质**：局部最优选择导向全局最优
2. **最优子结构**：问题可分解为相似子问题
3. **无后效性**：当前选择不影响未来选择的可行性（或影响可预测）
4. **计算效率要求**：需要快速决策，可接受近似解

常见贪心适用问题：
├── 活动安排问题（结束时间最早）
├── 霍夫曼编码（频率最小优先）
├── 最小生成树（Kruskal/Prim算法）
├── 单源最短路径（Dijkstra算法，非负权重）
└── 分数背包问题（价值密度最高优先）
​

"理解这些条件，"兔狲教授说，"帮助我们判断何时可以'贪心'，何时需要更复杂的策略。"

:::info
兔狲教授的评语
贪心算法的哲学是满意原则（Satisficing）而非最优原则（Optimizing）。它不追求绝对的最好，而是在可接受时间内找到足够好的解。这种思维方式在许多现实决策中很有用——无论是个人生活规划、商业策略制定，还是算法设计。
:::

关键要点

:::info
兔狲教授的总结：连续决策的贪心智慧

1. 贪心算法框架：在每一步选择当前最优候选，循环直至问题解决，体现短视但高效的决策风格
2. 正确性条件：贪心选择性质 + 最优子结构 = 全局最优保证；缺少任一条件则只能得到近似解
3. 适用场景识别：活动安排、最小生成树、霍夫曼编码等问题适合贪心；背包问题、旅行商问题等需要更复杂策略
4. 局部与全局的张力：贪心算法体现了局部最优与全局最优之间的永恒张力，提醒我们决策视野的重要性
5. 实践智慧：当问题具有贪心性质时，贪心算法是简洁优美的解；当不具备时，贪心是快速但可能次优的启发式
   :::

代码实践：贪心算法的Python实现

"让我们用代码来探索贪心算法的魅力与局限，"兔狲教授说，"从硬币找零到活动安排，从成功案例到失败反例。"

贪心算法通用框架

def greedy_algorithm_template(candidates, selection_rule, feasibility_check):
    """贪心算法通用模板
    
    问题描述:
        从候选集合中选择一个子集，满足某些约束条件，并优化某个目标。
    
    算法思路（贪心策略）:
        1. 初始化空解
        2. 当候选集合非空时循环：
           a. 使用选择规则从候选集中选出当前最优的候选
           b. 检查该候选加入当前解是否可行
           c. 如果可行，将其加入解中
           d. 从候选集中移除该候选
        3. 返回最终解
    
    关键特点:
        - 每一步都做出局部最优选择
        - 不回溯，不重新考虑已做的选择
        - 高效但可能不是全局最优
        - 适用于具有贪心选择性质的问题
    
    贪心选择性质:
        一个问题的全局最优解可以通过一系列局部最优选择得到。
        即：每一步的局部最优选择能导向全局最优解。
    
    参数:
        candidates: 候选集合（列表、集合等可迭代对象）
        selection_rule: 选择函数，接收候选集合，返回当前最优候选
        feasibility_check: 可行性检查函数，接收当前解和候选，返回布尔值
    
    返回:
        贪心解（列表形式）
    
    时间复杂度: 取决于选择规则和可行性检查的复杂度
    空间复杂度: O(n) - 存储解和候选集合
    
    示例（活动安排问题）:
        >>> activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
        >>> # 选择规则：选择结束时间最早的活动
        >>> def select_earliest_end(candidates):
        ...     return min(candidates, key=lambda x: x[1])
        >>> # 可行性检查：活动开始时间不早于上一个活动的结束时间
        >>> def is_feasible(solution, candidate):
        ...     if not solution:
        ...         return True
        ...     return candidate[0] >= solution[-1][1]
        >>> greedy_algorithm_template(activities, select_earliest_end, is_feasible)
        [(1, 4), (5, 7), (8, 11), (12, 16)]
    
    适用问题类型:
        - 活动安排问题（选择最多互不冲突的活动）
        - 霍夫曼编码（构建最优前缀码）
        - 最小生成树（Prim、Kruskal算法）
        - 硬币找零问题（特定面额下）
        - 任务调度问题
    """
    solution = []
    remaining_candidates = candidates.copy()
    
    while remaining_candidates:
        # 选择当前最优候选
        best_candidate = selection_rule(remaining_candidates)
        
        # 检查是否可行
        if feasibility_check(solution, best_candidate):
            solution.append(best_candidate)
        
        # 移除已处理的候选
        remaining_candidates.remove(best_candidate)
    
    return solution
​

硬币找零问题

def greedy_coin_change(amount, coins):
    """贪心硬币找零算法
    
    问题描述:
        给定一个金额和一组硬币面额，找出使用最少硬币凑出该金额的方法。
        假设每种硬币数量无限。
    
    算法思路（贪心策略）:
        1. 将硬币面额按降序排列（确保每次选择最大面额）
        2. 对于每种面额的硬币：
           a. 计算最多可以使用多少个这种硬币（不超过剩余金额）
           b. 使用尽可能多的这种硬币
           c. 更新剩余金额
        3. 如果最终金额减为0，返回硬币列表；否则返回None
    
    关键特点:
        - 每次选择当前可用的最大面额硬币
        - 对于某些面额组合（如[1, 5, 10, 25]）能得到最优解
        - 对于某些面额组合（如[1, 3, 4]）可能得不到最优解
        - 需要验证贪心选择性质是否成立
    
    贪心选择性质验证:
        对于硬币面额系统，贪心算法能得到最优解的条件是：
        每个较大面额都是较小面额的整数倍。
        例如：[1, 5, 10, 25]满足条件，[1, 3, 4]不满足。
    
    参数:
        amount: 需要凑出的金额（正整数）
        coins: 硬币面额列表（正整数列表，如[25, 10, 5, 1]）
    
    返回:
        使用的硬币列表（按面额从大到小），如果无法凑出则返回None
    
    时间复杂度: O(n)，其中n是硬币种类数
    空间复杂度: O(k)，其中k是使用的硬币数量
    
    示例:
        >>> greedy_coin_change(63, [25, 10, 5, 1])
        [25, 25, 10, 1, 1, 1]  # 使用6个硬币
        >>> greedy_coin_change(6, [4, 3, 1])
        [4, 1, 1]  # 贪心解使用3个硬币，但最优解是[3, 3]使用2个硬币
    
    注意:
        - 此算法不保证总是得到最少硬币数
        - 对于不满足贪心选择性质的面额系统，需要使用动态规划
        - 实际应用中需要检查面额系统的性质
    
    扩展:
        - 0-1硬币问题：每种硬币最多使用一次
        - 有限数量硬币：每种硬币有数量限制
        - 最小硬币数问题：动态规划解法保证最优
    """
    coins.sort(reverse=True)  # 降序排列，确保每次选最大面额
    result = []
    
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    
    if amount == 0:
        return result
    else:
        return None  # 无法凑出

def optimal_coin_change_dp(amount, coins):
    """动态规划硬币找零（对比贪心算法）
    
    参数:
        amount: 需要凑出的金额
        coins: 硬币面额列表
    
    返回:
        使用的最少硬币列表
    
    时间复杂度: O(amount * n)
    """
    # dp[i]表示凑出金额i所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    # 记录选择的硬币
    coin_used = [-1] * (amount + 1)
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                coin_used[i] = coin
    
    # 如果无法凑出
    if dp[amount] == float('inf'):
        return None
    
    # 回溯构造解
    result = []
    current = amount
    while current > 0:
        coin = coin_used[current]
        result.append(coin)
        current -= coin
    
    return result
​

硬币找零实验：贪心vs最优

def coin_change_experiment():
    """硬币找零问题实验：展示贪心算法的成功与失败"""
    
    print("硬币找零问题实验")
    print("=" * 50)
    
    # 测试用例
    test_cases = [
        ("标准货币系统（贪心最优）", 63, [100, 50, 20, 10, 5, 2, 1]),
        ("贪心失败的经典例子", 6, [4, 3, 1]),
        ("另一个失败案例", 30, [25, 10, 1]),
        ("复杂案例", 40, [25, 20, 10, 5, 1]),
    ]
    
    for name, amount, coins in test_cases:
        print(f"\n{name}:")
        print(f"  金额: {amount}, 硬币面额: {coins}")
        
        # 贪心算法
        greedy_result = greedy_coin_change(amount, coins.copy())
        if greedy_result:
            print(f"  贪心算法: {greedy_result} (使用{greedy_result}个硬币)")
        else:
            print(f"  贪心算法: 无法凑出")
        
        # 动态规划（最优解）
        optimal_result = optimal_coin_change_dp(amount, coins)
        if optimal_result:
            print(f"  最优算法: {optimal_result} (使用{len(optimal_result)}个硬币)")
        else:
            print(f"  最优算法: 无法凑出")
        
        # 比较
        if greedy_result and optimal_result:
            if len(greedy_result) == len(optimal_result):
                print(f"  结果: 贪心算法是最优的！")
            else:
                print(f"  结果: 贪心算法使用了{len(greedy_result)-len(optimal_result)}个额外硬币")

# 运行硬币找零实验
coin_change_experiment()
​

活动安排问题

def greedy_activity_selection(activities):
    """贪心活动安排算法（选择结束时间最早的活动）
    
    问题描述（活动安排问题）:
        给定n个活动，每个活动有开始时间start和结束时间end。
        选择最大的互不冲突的活动集合（即任意两个活动时间不重叠）。
        假设活动已经按结束时间排序。
    
    算法思路（贪心策略）:
        1. 将所有活动按结束时间升序排序
        2. 选择第一个活动（结束时间最早）
        3. 对于后续每个活动：
           a. 如果该活动的开始时间 ≥ 上一个选择活动的结束时间
           b. 选择该活动，更新上一个选择活动的结束时间
    
        贪心选择：每次选择结束时间最早且不与已选活动冲突的活动。
    
    正确性证明:
        1. 贪心选择性质：存在一个最优解包含结束时间最早的活动
        2. 最优子结构：选择某个活动后，剩余问题是最优子问题
        3. 归纳证明：通过数学归纳法证明贪心算法能得到最优解
    
    关键特点:
        - 经典贪心算法成功案例
        - 贪心选择能得到全局最优解
        - 时间复杂度主要来自排序
        - 需要活动按结束时间排序
    
    参数:
        activities: 活动列表，每个活动为(start, end)元组
                    start和end应为数值，且end > start
    
    返回:
        选择的活动列表（按选择顺序）
    
    时间复杂度: O(n log n) - 排序时间复杂度
    空间复杂度: O(n) - 存储排序后的活动和结果
    
    示例:
        >>> activities = [(1, 4), (3, 5), (0, 6), (5, 7), 
        ...               (3, 9), (5, 9), (6, 10), (8, 11),
        ...               (8, 12), (2, 14), (12, 16)]
        >>> greedy_activity_selection(activities)
        [(1, 4), (5, 7), (8, 11), (12, 16)]
        
        解释：
        1. 按结束时间排序后：[(1,4), (3,5), (0,6), (5,7), ...]
        2. 选择(1,4)，最后结束时间=4
        3. 下一个开始时间≥4的是(5,7)，选择，最后结束时间=7
        4. 下一个开始时间≥7的是(8,11)，选择，最后结束时间=11
        5. 下一个开始时间≥11的是(12,16)，选择
        共选择4个活动
    
    注意:
        - 活动时间应为半开区间[start, end)，即end时刻可以开始下一个活动
        - 如果活动未排序，需要先排序
        - 此算法选择的是最大数量的活动，不一定是最大总时长的活动
    
    变体问题:
        - 带权活动选择：每个活动有权重，求最大权重和
        - 资源受限：有多个资源（房间），求最多安排的活动
        - 时间区间重叠：允许一定重叠
    
    应用场景:
        - 会议室安排
        - 课程表安排
        - 任务调度
        - 电视节目安排
    """
    # 按结束时间排序
    sorted_activities = sorted(activities, key=lambda x: x[1])
    
    selected = []
    last_end_time = 0
    
    for start, end in sorted_activities:
        if start >= last_end_time:  # 活动不冲突
            selected.append((start, end))
            last_end_time = end
    
    return selected

def greedy_activity_selection_alternative(activities, key='end'):
    """不同选择标准的贪心活动安排
    
    参数:
        activities: 活动列表
        key: 排序标准，'start'(开始时间最早), 'duration'(持续时间最短), 'end'(结束时间最早)
    
    返回:
        选择的活动列表
    """
    if key == 'start':
        # 按开始时间排序
        sorted_activities = sorted(activities, key=lambda x: x[0])
    elif key == 'duration':
        # 按持续时间排序
        sorted_activities = sorted(activities, key=lambda x: x[1] - x[0])
    else:  # 'end'
        sorted_activities = sorted(activities, key=lambda x: x[1])
    
    selected = []
    last_end_time = 0
    
    for start, end in sorted_activities:
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end
    
    return selected
​

活动安排实验

def activity_selection_experiment():
    """活动安排问题实验：比较不同贪心策略"""
    
    print("\n" + "=" * 50)
    print("活动安排问题实验")
    print("=" * 50)
    
    # 测试数据
    activities = [
        (1, 4), (3, 5), (0, 6), (5, 7),
        (3, 8), (5, 9), (6, 10), (8, 11),
        (8, 12), (2, 13), (12, 14)
    ]
    
    print(f"活动列表: {activities}")
    print(f"活动数量: {len(activities)}")
    
    # 不同策略比较
    strategies = ['start', 'duration', 'end']
    
    for strategy in strategies:
        selected = greedy_activity_selection_alternative(activities, strategy)
        print(f"\n按'{strategy}'排序选择的活动:")
        print(f"  选择的活动: {selected}")
        print(f"  活动数量: {len(selected)}")
    
    # 最优性验证（结束时间最早策略是最优的）
    print("\n" + "=" * 50)
    print("贪心选择性质验证")
    print("=" * 50)
    
    print("定理证明思路:")
    print("1. 贪心选择性质: 第一个选择结束时间最早的活动一定在某个最优解中")
    print("2. 最优子结构: 选择第一个活动后，剩余问题与原问题结构相同")
    print("3. 数学归纳法: 结合1和2，贪心算法得到全局最优解")
    
    # 可视化证明
    sorted_by_end = sorted(activities, key=lambda x: x[1])
    print(f"\n活动按结束时间排序: {sorted_by_end}")
    
    print("\n贪心算法步骤:")
    last_end = 0
    for i, (start, end) in enumerate(sorted_by_end):
        if start >= last_end:
            print(f"  步骤{i+1}: 选择活动({start}, {end})，因为开始时间{start} >= 上一个活动结束时间{last_end}")
            last_end = end
​

霍夫曼编码（贪心构造最优前缀码）

import heapq

class HuffmanNode:
    """霍夫曼树节点"""
    def __init__(self, char=None, freq=0):
        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(frequencies):
    """构建霍夫曼树（贪心算法）
    
    参数:
        frequencies: 字典，字符->频率
    
    返回:
        霍夫曼树的根节点
    
    算法步骤:
        1. 为每个字符创建叶子节点，放入最小堆
        2. 当堆中有超过一个节点时:
           a. 弹出两个频率最小的节点
           b. 创建新节点，频率为两者之和，左右子节点为这两个节点
           c. 将新节点压入堆中
        3. 堆中剩下的唯一节点就是霍夫曼树的根
    """
    # 创建叶子节点堆
    heap = [HuffmanNode(char, freq) for char, freq in frequencies.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        # 弹出两个频率最小的节点
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        
        # 创建新节点
        merged = HuffmanNode(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        # 压入堆中
        heapq.heappush(heap, merged)
    
    return heap[0] if heap else None

def generate_huffman_codes(root, current_code="", codes={}):
    """生成霍夫曼编码
    
    参数:
        root: 霍夫曼树根节点
        current_code: 当前路径编码
        codes: 编码字典
    
    返回:
        字符->编码的字典
    """
    if root is None:
        return codes
    
    # 叶子节点，记录编码
    if root.char is not None:
        codes[root.char] = current_code
        return codes
    
    # 递归遍历左右子树
    generate_huffman_codes(root.left, current_code + "0", codes)
    generate_huffman_codes(root.right, current_code + "1", codes)
    
    return codes

def huffman_coding_example():
    """霍夫曼编码示例"""
    
    print("\n" + "=" * 50)
    print("霍夫曼编码（贪心构造最优前缀码）")
    print("=" * 50)
    
    # 示例：英文文本中字母频率
    frequencies = {
        'a': 45,  # 最高频率
        'b': 13,
        'c': 12,
        'd': 16,
        'e': 9,
        'f': 5,
    }
    
    print(f"字符频率: {frequencies}")
    
    # 构建霍夫曼树
    root = build_huffman_tree(frequencies)
    
    # 生成编码
    codes = generate_huffman_codes(root)
    
    print("\n生成的霍夫曼编码:")
    for char, code in sorted(codes.items()):
        print(f"  '{char}': {code} (频率: {frequencies[char]})")
    
    # 计算平均编码长度
    total_freq = sum(frequencies.values())
    avg_length = sum(frequencies[char] * len(code) for char, code in codes.items()) / total_freq
    
    print(f"\n平均编码长度: {avg_length:.2f}比特/字符")
    print(f"固定长度编码需要: {len(bin(len(frequencies)-1))-2}比特/字符")
    
    # 贪心性质验证
    print("\n贪心性质验证:")
    print("合并频率最小的两个节点总是最优的，因为:")
    print("1. 频率低的字符应该编码长，频率高的字符应该编码短")
    print("2. 合并最小频率节点相当于给它们分配最长的编码路径")
    print("3. 数学归纳法可以证明这个贪心策略得到全局最优前缀码")

# 运行霍夫曼编码示例
huffman_coding_example()
​

兔狲教授总结道，"我们不仅理解了贪心算法的实现，更理解了连续决策的策略。贪心算法教给我们：有时候，最好的长期策略是一系列好的短期决策；但有时候，短视会导致灾难。知道何时贪心、何时规划，是算法思维也是生活智慧。"

兔狲教授的思考题

实践探索（适合小小猪）

1. 算法实现：实现活动安排问题的贪心算法。测试不同排序标准（开始时间最早、持续时间最短、结束时间最早）的结果。哪个标准能得到最优解？为什么？

2. 贪心失败构造：构造一个使贪心算法严重失败的问题实例。例如：设计一组硬币面额，使得贪心凑零钱算法使用的硬币数远多于最优解。

3. 现实观察：观察生活中的贪心决策。超市结账时选择最短队伍是贪心策略吗？什么时候会失败？（提示：考虑队伍中顾客购物车内容）

历史探究（适合小海豹）

1. 思想溯源："贪心"（Greedy）这个概念在计算机科学中何时出现？最早是谁提出并分析了贪心算法？查阅早期算法文献（如Kruskal 1956, Prim 1957, Dijkstra 1959）。

2. 跨学科联系：贪心算法与经济学中的"边际决策"、心理学中的"即时满足"有什么相似之处？这些领域如何研究短视决策的利弊？

3. 哲学反思：功利主义的"最大幸福原则"是贪心思维吗？边沁和密尔的功利主义与贪心算法有什么相似和不同？

综合思考

1. 伦理考量：自动驾驶汽车在紧急情况下的决策可以用贪心算法吗？（例如：总是选择最小化立即伤害的转向）这种短视决策可能有什么问题？

2. 算法比较：贪心算法与动态规划（下章内容）有什么根本区别？为什么有些问题贪心有效而动态规划需要？有些则相反？

3. 创造练习：设计一个"贪心寓言"——用故事解释贪心算法的优点和局限。（提示：可以比喻为登山者总是选择最陡的上坡路）

4. 极限挑战：证明霍夫曼编码的贪心算法最优性。理解为什么合并频率最小的节点总是最优的。

下一步预告

傍晚的珠江泛起金色的波光，游船缓缓驶过，留下长长的水痕。康乐园的钟声再次响起，提醒着时间的流逝。

小小猪正在电脑上模拟不同贪心策略的效果，屏幕上显示着各种问题实例和算法表现。小海豹则在白板上推导贪心选择性质的证明，试图理解那看似直觉的选择背后的数学必然。

"今天我们从'连续决策的策略'开始，"兔狲教授收拾着茶具，"探索了贪心算法的智慧与局限，理解了局部最优与全局最优的张力。"

小海豹放下粉笔，"教授，如果贪心算法可能失败，我们有什么方法能保证得到全局最优解呢？"

兔狲教授微笑："好问题。这就需要更强大的工具了——启发式。"

小小猪的笔记：我测试了不同硬币系统的贪心算法。对于常见面额（1,2,5,10,20,50,100），贪心总是最优！但对于奇怪的面额（1,3,4），要付6元时贪心选4+1+1（3个硬币），最优是3+3（2个硬币）。原来我们用的货币系统是精心设计的！

小海豹的笔记：查了贪心算法的历史，发现Kruskal和Prim在1950年代独立提出最小生成树算法，都用了贪心思想。有时，简单的直觉需要时间才能形式化证明。

兔狲教授的结语：记住，贪心算法教给我们决策的重要一课：有时候，最好的长期策略是一系列好的短期决策；但有时候，短视会导致灾难。知道何时贪心、何时规划，是算法思维也是生活智慧。我们慢慢来，理解了最重要。