python数据结构学习笔记-树（下）-哈夫曼树与哈夫曼编码（1）

哈夫曼树

带权路径长度（WPL）

二叉树中所有叶结点的带权路径长度之和，其中n为叶节点数，根节点要叶节点的长度为l：
$WPL = \sum_{k=1}^{n}w_kl_k\quad$WPL=k=1∑n​wk​lk​
哈夫曼树即最优二叉树，指WPL最小的二叉树。
哈夫曼树的每个节点的度为0或2.

哈夫曼树的构造

每次把权值最小的两颗二叉树合并（利用堆排序来选择权值的最小值）

def insert_data(heap, x):
    if len(heap.data) > heap.maxsize:       # 判断堆是否已满
        print('Full')
    else:
        heap.size += 1
        heap.data.append(x)        # 先放在数组的最后
        i = heap.size
        while i:
            if x < heap.data[i//2]:        # 比较插入点与父节点的大小，比父节点小即与父节点交换
                heap.data[i] = heap.data[i//2]
                heap.data[i//2] = x
                i //= 2
            else:
                break
    return heap


def delete_data(heap):
    if len(heap.data) == 1:        # 判断堆是否已空
        print('Empty')
    else:
        data = heap.data[1]         # 根节点即最小值
        temp = heap.data[heap.size]         # 把最后一个元素提出
        heap.data.pop()
        heap.size -= 1
        parent = 1
        while parent*2 <= heap.size:
            child = parent * 2
            if child != heap.size and heap.data[child] > heap.data[child+1]:
                child += 1
            if temp < heap.data[child]:
                break
            else:
                heap.data[parent] = heap.data[child]
                parent = child
            heap.data[parent] = temp
        return data


class Heap:
    def __init__(self):
        self.size = 0       # 当前容量
        self.maxsize = 0        # 堆的最大容量
        self.data = [0]      # 存储堆元素的数组


# 建立最小堆
min_heap = Heap()
min_heap.maxsize = 10
min_heap.data[0] = -10000      # 放一个比所有元素都小的值，做哨兵
weight = [1, 6, 5, 7, 8, 4, 9, 3, 10, 2]     # 权重列表
for i in range(10):
    insert_data(min_heap, weight[i])
print(min_heap.data)

tree = list()
for i in range(min_heap.maxsize):
    node = dict(data=0, left=0, right=0)
    node['left'] = delete_data(min_heap)    # 取出最小的两个权重值（最小堆的根节点）
    node['right'] = delete_data(min_heap)
    if len(min_heap.data) == 1:
        break
    node['data'] = node['left'] + node['right']     # 权值相加为新的节点权值
    tree.append(node)
    insert_data(min_heap, node['data'])     # 新权值与原权值一起重新排序

print(tree)

哈夫曼编码

不等长编码，出现频率大的编码长度短，反之编码长度长。
需避免二义性：任何一个字符的编码都不是其他字符编码的前缀码。
因此可以使用二叉树：根节点的左右分支为0，1，而字符只在叶节点上。