Python 最小堆实现Huffman树

系统管理员 2022-05-18 03:41 246阅读 0赞

Huffman树又称**最优二叉树**，是一类加权路径长度最短的二叉树。

给出n个实数![W\_\{\_\{0\}\},W\_\{\_\{1\}\},\\cdots ,W\_\{\_\{n-1\}\}\\left ( n\\geqslant 2 \\right ),][W_0_W_1_cdots _W_n-1_left _ n_geqslant 2 _right]要求得到一个具有n个外部结点的扩充二叉树，该扩充二叉树的每个外部结点![k\_\{i\}][k_i]有一个![W\_\{i\}][W_i]与之对应，作为结点![k\_\{i\}][k_i]的权值，使得带权外部路径长度![WPL=\\sum\_\{i=0\}^\{n-1\}W\_\{i\}l\_\{i\}][WPL_sum_i_0_n-1_W_i_l_i]为最小，其中![l\_\{i\}][l_i]是从根到外部结点![k\_\{i\}][k_i]的路径长度。

结论——**权越大**的叶结点**离根越近**；如果某个叶结点的**权较小**，可能就会**离根较远**。

Huffman树的构建方法：

(1) 根据给定的 n 个权值![\\left \\\{ w\_\{1\},w\_\{2\},\\cdots ,w\_\{n-1\} \\right \\\}\\left ( n\\geqslant 2 \\right )][left _ w_1_w_2_cdots _w_n-1_ _right _left _ n_geqslant 2 _right] 构成 n 棵二叉树的集合![F=\\left \\\{ T\_\{1\}, T\_\{2\}, \\cdots , T\_\{n\}\\right \\\}][F_left _ T_1_ T_2_ _cdots _ T_n_right] ，其中每棵二叉树 ![T\_\{i\}][T_i]中只有一个权值为![W\_\{i\}][W_i]的根结点。

(2) 在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。

(3) 在 F 中删除这两棵树，同时将新得到的二叉树加入集合 F 中。

(4) 重复 (2) 和 (3) ，直到 F 中只含一棵树为止。

其中最小树集合可以使用最小堆算法来实现。

例如字符权重对数组 array= \[\['a',5\],\['b',29\],\['c',7\],\['d',8\],\['e',14\],\['f',23\],\['g',3\],\['h',11\]\]，构造huffuman树如图所示

![70][]

代码实现

import queue
    '''
    Huffman树结点类
    '''
    class HuffmanTreeNode(object):
        def __init__(self,val=' ',weight = 0,left=None,right=None):
            self.val = val
            self.weight = weight
            self.left = left
            self.right = right
    '''
    最小堆
    '''
    class MinHeap():
        def __init__(self,n = 0):
            self.size = 0
            self.p = [HuffmanTreeNode()]*n
        def getparentnode(self,pos):#获取父结点
            if((pos-1)/2 >=0):
                return int((pos-1)/2)
            else:
                return 0
        def SiftUp(self,pos):#向上调整
            if(pos>0):
                tmppos = pos
                tmp = self.p[pos]
                while(tmppos>0 and tmp.weight<self.p[self.getparentnode(tmppos)].weight):
                    self.p[tmppos] = self.p[self.getparentnode(tmppos)]
                    tmppos = self.getparentnode(tmppos)
                self.p[tmppos] = tmp
        def Insert(self,node):#插入结点
            self.p[self.size] = node
            self.size += 1
            self.SiftUp(self.size-1)
        def RemoveMin(self):#移除最小值
            minnode = self.p[0]
            self.p[0] = self.p[self.size - 1]
            self.size -= 1
            tmp = self.p[0]
            i = 0
            j = 2*i + 1 #完全二叉树的子结点
            while(j<self.size):
                if(j<self.size-1 and self.p[j].weight > self.p[j+1].weight):
                    j += 1
                if(tmp.weight > self.p[j].weight):
                    self.p[i] = self.p[j]
                    i = j
                    j = 2*i + 1
                else: break
            self.p[i] = tmp      
            return minnode
    
    def MergeTree(firstchild,secondchild,parent):#合并树
        parent.left = firstchild
        parent.right = secondchild
        parent.weight = firstchild.weight + secondchild.weight
        return parent
    '''
    构建Huffman树
    '''
    def BuildHuffanTree(treenodearray):
        n = len(treenodearray)
        root = HuffmanTreeNode()
        heap = MinHeap(n)#最小堆维护huffumantree的n棵二叉树集合的根节点
        for i in range(n):
            node = HuffmanTreeNode(val = treenodearray[i][0],weight=treenodearray[i][1])
            heap.Insert(node)
        p = heap.p
        print('生成的最小堆：',end=' ')
        for i in range(heap.size):
            print(p[i].val,end='-')
            print(p[i].weight,end='\t')
        print()
        for i in range(n-1):
            parent = HuffmanTreeNode()
            firstchild = heap.RemoveMin()
            secondchild = heap.RemoveMin()
            parent = MergeTree(firstchild, secondchild, parent)
            heap.Insert(parent)
            root = parent
        return root

测试代码

if __name__ == '__main__':
        treenodearray = [['a',5],['b',29],['c',7],['d',8],['e',14],['f',23],['g',3],['h',11]]
        root = BuildHuffanTree(treenodearray)
        tmp = root
        print('生成的HuffmanTree广度优先遍历:',end=' ')
        levelOrder(tmp)
        print()
        print('生成的HuffmanTree递归前序遍历:',end=' ')
        RecursionPreOrder(root)
        print()
        print('生成的HuffmanTree递归中序遍历:',end=' ')
        RecursionInOrder(tmp)
        print()
        encodedict = {}
        rootcode = [root,'']
        deque = queue.Queue()
        deque.put(rootcode)
        while(not deque.empty()):#对字符生成Huffman编码
            node = deque.get()
            treenode = node[0]
            strnode = node[1]
            if(treenode.left is not None):
                deque.put([treenode.left,strnode+'0'])
            if(treenode.right is not None):
                deque.put([treenode.right,strnode+'1'])
            if(treenode.left is None and treenode.right is None):
                encodedict.setdefault(treenode.val,strnode)
        for key in encodedict.keys():
            print(key,end='--')
            print(encodedict[key])

输出结果

生成的最小堆： g-3	d-8	a-5	h-11	e-14	f-23	c-7	b-29	
    生成的HuffmanTree广度优先遍历: 100 42 58 19 23 29 29 8 11 14 15 3 5 7 8 
    生成的HuffmanTree递归前序遍历: 100 42 19 8 3 5 11 23 58 29 14 15 7 8 29 
    生成的HuffmanTree递归中序遍历: 3 8 5 19 11 42 23 100 14 29 7 15 8 58 29 
    g--0000
    h--001
    c--1010
    b--11
    a--0001
    e--100
    d--1011
    f--01

[W_0_W_1_cdots _W_n-1_left _ n_geqslant 2 _right]: https://private.codecogs.com/gif.latex?W_%7B_%7B0%7D%7D%2CW_%7B_%7B1%7D%7D%2C%5Ccdots%20%2CW_%7B_%7Bn-1%7D%7D%5Cleft%20%28%20n%5Cgeqslant%202%20%5Cright%20%29%2C
[k_i]: https://private.codecogs.com/gif.latex?k_%7Bi%7D
[W_i]: https://private.codecogs.com/gif.latex?W_%7Bi%7D
[WPL_sum_i_0_n-1_W_i_l_i]: https://private.codecogs.com/gif.latex?WPL%3D%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DW_%7Bi%7Dl_%7Bi%7D
[l_i]: https://private.codecogs.com/gif.latex?l_%7Bi%7D
[left _ w_1_w_2_cdots _w_n-1_ _right _left _ n_geqslant 2 _right]: https://private.codecogs.com/gif.latex?%5Cleft%20%5C%7B%20w_%7B1%7D%2Cw_%7B2%7D%2C%5Ccdots%20%2Cw_%7Bn-1%7D%20%5Cright%20%5C%7D%5Cleft%20%28%20n%5Cgeqslant%202%20%5Cright%20%29
[F_left _ T_1_ T_2_ _cdots _ T_n_right]: https://private.codecogs.com/gif.latex?F%3D%5Cleft%20%5C%7B%20T_%7B1%7D%2C%20T_%7B2%7D%2C%20%5Ccdots%20%2C%20T_%7Bn%7D%5Cright%20%5C%7D
[T_i]: https://private.codecogs.com/gif.latex?T_%7Bi%7D
[70]: /images/20220518/2c5bf253a009477e8e3be41def36d8a0.png