零基础数据结构与算法——第五章：高级算法-贪心算法-分数背包&霍夫曼编码

5.2.2 经典贪心算法问题（下）

分数背包问题

问题描述：有n个物品，每个物品有重量和价值。现在有一个容量为W的背包，每个物品可以取部分，求解如何选择物品放入背包，使得背包中物品的总价值最大。

贪心解法：按照物品的单位价值（价值/重量）排序，优先选择单位价值高的物品。

public static double fractionalKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    Item[] items = new Item[n];
    
    for (int i = 0; i < n; i++) {
        items[i] = new Item(weights[i], values[i]);
    }
    
    // 按单位价值排序（降序）
    Arrays.sort(items, (a, b) -> Double.compare(b.valuePerWeight, a.valuePerWeight));
    
    double totalValue = 0;
    int remainingCapacity = capacity;
    
    for (int i = 0; i < n; i++) {
        if (remainingCapacity >= items[i].weight) {
            // 可以完全放入
            totalValue += items[i].value;
            remainingCapacity -= items[i].weight;
        } else {
            // 只能放入一部分
            totalValue += items[i].valuePerWeight * remainingCapacity;
            break;
        }
    }
    
    return totalValue;
}

static class Item {
    int weight, value;
    double valuePerWeight;
    
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.valuePerWeight = (double) value / weight;
    }
}

霍夫曼编码

问题描述：

给定一组字符及其出现频率，设计一种变长编码方式，使得编码后的总长度最小，且任何字符的编码都不是其他字符编码的前缀（前缀码）。

生活例子：

想象你是一名电报操作员，需要用摩尔斯电码传输消息。为了提高传输效率，你希望为常用字符（如’e’、‘t’）分配较短的编码，为不常用字符（如’z’、‘q’）分配较长的编码。这样，整体传输的电码长度就会更短。

问题分析：

如果所有字符的编码长度相同（如ASCII码），那么编码后的总长度就是字符数乘以编码长度。但如果允许不同字符有不同的编码长度，我们可以通过为高频字符分配短编码，为低频字符分配长编码，来减少总长度。

霍夫曼编码的关键是构建一棵霍夫曼树，然后根据树的路径生成编码：

• 左子树路径表示0
• 右子树路径表示1
• 从根节点到叶节点的路径就是该字符的编码

贪心策略：使用最小堆构建霍夫曼树，频率低的字符编码长，频率高的字符编码短。

图解过程：

假设有以下字符及其频率：

A: 5
B: 9
C: 12
D: 13
E: 16
F: 45

构建霍夫曼树的步骤：

1. 创建一个最小堆，包含所有字符节点，按频率排序：

   [A:5, B:9, C:12, D:13, E:16, F:45]

2. 取出两个频率最小的节点（A和B），创建一个新节点AB，频率为两者之和：

   AB:14
   /  \
  A:5  B:9

堆变为：[C:12, D:13, AB:14, E:16, F:45]

3. 取出两个频率最小的节点（C和D），创建一个新节点CD：

   CD:25
   /  \
  C:12 D:13

堆变为：[AB:14, E:16, CD:25, F:45]

4. 取出两个频率最小的节点（AB和E），创建一个新节点ABE：

    ABE:30
    /   \
   AB:14 E:16
   /  \
  A:5  B:9

堆变为：[CD:25, ABE:30, F:45]

5. 取出两个频率最小的节点（CD和ABE），创建一个新节点CDABE：

      CDABE:55
      /     \
    CD:25   ABE:30
    /  \    /   \
   C:12 D:13 AB:14 E:16
             /  \
            A:5  B:9

堆变为：[F:45, CDABE:55]

6. 取出两个频率最小的节点（F和CDABE），创建根节点：

          ROOT:100
          /     \
        F:45   CDABE:55
               /     \
             CD:25   ABE:30
             /  \    /   \
            C:12 D:13 AB:14 E:16
                      /  \
                     A:5  B:9

根据霍夫曼树生成编码（左0右1）：

F: 0
C: 10
D: 11
A: 100
B: 101
E: 11

代码实现：

public static Map<Character, String> huffmanCoding(char[] chars, int[] freq) {
    int n = chars.length;
    PriorityQueue<HuffmanNode> minHeap = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    
    // 创建叶节点并加入最小堆
    for (int i = 0; i < n; i++) {
        minHeap.add(new HuffmanNode(chars[i], freq[i]));
    }
    
    // 构建霍夫曼树
    System.out.println("构建霍夫曼树过程：");
    while (minHeap.size() > 1) {
        HuffmanNode left = minHeap.poll();
        HuffmanNode right = minHeap.poll();
        
        int sumFreq = left.freq + right.freq;
        HuffmanNode parent = new HuffmanNode('\0', sumFreq);
        parent.left = left;
        parent.right = right;
        
        System.out.println("合并节点：" + nodeToString(left) + " 和 " + nodeToString(right) + 
                         " -> 新节点频率：" + sumFreq);
        
        minHeap.add(parent);
    }
    
    // 从霍夫曼树生成编码
    Map<Character, String> codes = new HashMap<>();
    generateCodes(minHeap.peek(), "", codes);
    
    // 打印编码结果
    System.out.println("\n霍夫曼编码结果：");
    for (Map.Entry<Character, String> entry : codes.entrySet()) {
        System.out.println(entry.getKey() + ": " + entry.getValue() + 
                         " (频率: " + getFrequency(entry.getKey(), chars, freq) + ")");
    }
    
    return codes;
}

private static String nodeToString(HuffmanNode node) {
    if (node.data == '\0') {
        return "内部节点:" + node.freq;
    } else {
        return "'" + node.data + "':" + node.freq;
    }
}

private static int getFrequency(char c, char[] chars, int[] freq) {
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == c) {
            return freq[i];
        }
    }
    return 0;
}

private static void generateCodes(HuffmanNode root, String code, Map<Character, String> codes) {
    if (root == null) return;
    
    // 如果是叶节点，添加编码
    if (root.left == null && root.right == null && root.data != '\0') {
        codes.put(root.data, code);
    }
    
    generateCodes(root.left, code + "0", codes);
    generateCodes(root.right, code + "1", codes);
}

static class HuffmanNode {
    char data;  // 字符
    int freq;   // 频率
    HuffmanNode left, right;  // 左右子节点
    
    public HuffmanNode(char data, int freq) {
        this.data = data;
        this.freq = freq;
        this.left = this.right = null;
    }
}

时间复杂度：O(n log n)，其中n是字符数量。构建最小堆需要O(n)时间，从堆中取出和插入元素需要O(log n)时间，总共需要n-1次合并操作。

空间复杂度：O(n)，用于存储霍夫曼树和编码表。

应用场景：

1. 数据压缩：霍夫曼编码是许多压缩算法的基础，如ZIP、JPEG等。
2. 电信编码：在通信系统中用于减少传输数据量。
3. 数据存储：减少存储空间需求。

优缺点：

优点：

• 能够根据字符频率自适应生成最优编码
• 解码过程唯一（前缀码特性）
• 压缩效率高

缺点：

• 需要存储或传输编码表
• 如果频率分布均匀，压缩效果不明显
• 编码和解码过程相对复杂

5.2.3 贪心算法与动态规划的比较