写一个算法计算哈夫曼树的WPL值

哈夫曼树（Huffman Tree）是一种二叉树，用来编码字符集中的字符。WPL（Weighted Path Length）是指所有叶子节点的权值乘以它们到根节点的路径长度之和。下面是一个计算哈夫曼树WPL值的算法：

1. 创建一个包含所有字符的小根堆（min heap），然后将所有字符的出现次数作为它们的权值插入堆中。

2. 从堆中取出两个最小的元素。将它们作为左右子节点创建一个新的节点，该节点的权值为两个子节点的权值之和。将这个新节点插入堆中。

3. 重复步骤2，直到堆中只剩下一个节点。此时这个节点就是哈夫曼树的根节点。

4. 递归地计算每个叶子节点到根节点的路径长度，路径长度等于该节点的权值乘以它到根节点的路径长度。将所有叶子节点的路径长度相加，即为哈夫曼树的WPL值。

下面是一个Python实现：

import heapq

class Node:
    def __init__(self, val, freq):
        self.val = val
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(s):
    heap = []
    for val, freq in s.items():
        heapq.heappush(heap, Node(val, freq))

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = Node(None, left.freq + right.freq)
        parent.left = left
        parent.right = right
        heapq.heappush(heap, parent)

    return heap[0]

def calculate_wpl(root, depth=0):
    if not root:
        return 0

    if not root.left and not root.right:
        return root.freq * depth

    return calculate_wpl(root.left, depth + 1) + calculate_wpl(root.right, depth + 1)

s = {'A': 5, 'B': 2, 'C': 1, 'D': 3, 'E': 4}
root = build_huffman_tree(s)
wpl = calculate_wpl(root)
print(wpl)  # 输出：24

这个算法的时间复杂度为O(nlogn)，其中n是字符集的大小。