1. 题目要求

    • 种字符的字符串
    • 每种字符出现次数为
    • 求哈夫曼编码后的最短长度

  2. 哈夫曼编码原理

    • 出现频率高的字符用短编码
    • 出现频率低的字符用长编码
    • 构建二叉树来得到编码

解题思路

  1. 核心算法

    1. 每次选择两个最小的频率合并
2. 合并后的频率为两者之和
3. 重复此过程直到只剩一个节点
4. 每次合并会使编码长度增加两个数的和

  2. 使用优先队列

    • 维护一个最小堆
    • 每次取出两个最小值
    • 将和放回堆中

代码

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 使用优先队列（最小堆）
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    
    // 读入频率
    for(int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }
    
    long long result = 0;
    // 当队列中至少有两个元素时
    while(pq.size() > 1) {
        // 取出两个最小值
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        // 计算编码长度增量并加入结果
        result += a + b;
        // 将和放回队列
        pq.push(a + b);
    }
    
    cout << result << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读入字符种数
        int n = sc.nextInt();
        
        // 使用优先队列（最小堆）
        PriorityQueue<Long> pq = new PriorityQueue<>();
        
        // 读入每个字符的频率
        for(int i = 0; i < n; i++) {
            long freq = sc.nextLong();
            pq.offer(freq);
        }
        
        long result = 0;
        
        // 当队列中至少有两个元素时继续合并
        while(pq.size() > 1) {
            // 取出两个最小值
            long a = pq.poll();
            long b = pq.poll();
            
            // 计算编码长度增量并加入结果
            result += a + b;
            
            // 将和放回队列
            pq.offer(a + b);
        }
        
        System.out.println(result);
    }
}

import heapq

n = int(input())
nums = list(map(int, input().split()))

# 构建最小堆
heapq.heapify(nums)

result = 0
# 当堆中至少有两个元素时
while len(nums) > 1:
    # 取出两个最小值
    a = heapq.heappop(nums)
    b = heapq.heappop(nums)
    # 计算编码长度增量并加入结果
    result += a + b
    # 将和放回堆中
    heapq.heappush(nums, a + b)

print(result)

算法及复杂度分析

算法：贪心+优先队列

时间复杂度

  • 建堆：
  • 每次操作：
  • 总操作次数：
  • 总时间复杂度：

空间复杂度

  • 优先队列存储：

注意事项

  1. 数据范围

    • 需要使用 类型

  2. 优先队列使用

    • C++：
    • Python：
    • Java：

  3. 边界情况

    • 时直接输出
    • 注意数据溢出