哈夫曼编码

贪心

说明

每次合并频率最小的两棵树；得到最小加权路径长度。

分析

频率较低的符号应放在较深位置；每次把当前最小的两个权重合并成一个父节点，形成最小加权路径长度。示例只计算总代价，真正编码还需保存树结构并从根生成 0/1 编码。

图解推演

频率 [5,9,12,13] 先合并 5+9=14，再合并 12+13=25，最后合并 14+25=39，总代价 14+25+39=78。每次合并使子树所有叶子深度加一，新增代价正好是子树权重之和，因此合并代价等于加权路径长度。生成码字还需沿树边记录 0/1。

查看图表代码

适用前提与边界

反复排序便于理解，使用最小堆可更高效。

示例输入与调用

fmt.Println(HuffmanCost([]int{5, 9, 12, 13}))

运行输出

78

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

func HuffmanCost(freq []int) int {
	h := append([]int(nil), freq...)
	cost := 0
	for len(h) > 1 {
		sort.Ints(h)
		merged := h[0] + h[1]
		cost += merged
		h = append(h[2:], merged)
	}
	return cost
}

func main() {
	fmt.Println(HuffmanCost([]int{5, 9, 12, 13}))
}