概念

假设我们有一组百分制的考试分数, 想转换成 5 个等级, A >= 90, 80 <= B < 90, 70 <= C < 80, 60 <= D < 70, E < 60

我们可以很容易写出这样的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
switch {
case point >= 90:
    return 'A'
case point < 90 && point >= 80:
    return 'B'
case point < 80 && point >= 70:
    return 'C'
case point < 70 && point >= 60:
    return 'D'
default:
    return 'E'
}

这样我们便得到这样一个二叉树, 对于等级 ‘A’ 来说需要查找 5 次

学生成绩判定树
学生成绩判定树

考虑下面一次分数占比情况, 则查找效率为 $0.05 * 1 + 0.15 * 2 + 0.5 * 3 + 0.2 * 4 + 0.1 * 5 = 3.15 $, 占比少的需要查的次数少, 而占比多的却需要查的次数多, 查找效率不高

分数0-5960-6970-7980-8990-100
比例0.050.150.50.20.1

我们把分数的比例称为权重, 这样我们就可以构造出一棵带权重的树, 权重大的查找次数少, 权重低的查找次数多, 哈夫曼树便是这样一棵带权重的二叉树, 其查找效率 $WPL = \sum_{k=1}^{n}w_k*l_k $ (w 是权重, k 是查找次数) 为最小

哈夫曼树的构造

  1. 在一组数中, 选出两个权重最小的数, 为左右结点, 其和为父结点
  2. 在第一步中得到的树, 父结点和剩余的数组成新序列, 重复上个步骤
  3. 直到序列中再没有数

构造哈夫曼树
构造哈夫曼树

构造一棵哈夫曼树的最重要是如何每次选取到最小的值, 一种方法是将所有的数据进行排序, 这样选取前两个最小值即可. 另一种是很一个最小堆, 因为我们只关心最小值, 其他数值的顺序并没有关系, 这样每次生成的父结点加入到最小堆中, 堆重新排序, 取出头结点即可, 比将所有数据重新排序效率更快

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func CreateHuffmanTree(arr []interface{}, cmp EqualFunc) *HuffmanTree {
	queue := CreateQueue(arr, cmp)
	tree := &HuffmanTree{}
	for queue.Size > 0 {
		// 每次取出堆中两个最小值
		n1, _ := queue.Pop()
		n2, _ := queue.Pop()
		// 组成一棵树
		parent := ch03.TreeNode{Data: n1.Data.(int) + n2.Data.(int)}
		if cmp(&n1, &n2) > 0 {
			parent.Left = &n1
			parent.Right = &n2
		} else {
			parent.Left = &n2
			parent.Right = &n1
		}

		if queue.Size == 0 {
			tree.Root = &parent
			break
		}

		// 结点新压回堆中
		_ = queue.Push(parent)
	}

	return tree
}

代码地址: https://github.com/ivicel/zju-data-structure

Reference