【蓝桥python冲刺14天】——周末营养加餐(哈夫曼树模板)

 大家好,我是爱分享的小蓝,欢迎交流指正~ 

全文目录?

?哈夫曼树-模板

?题目描述

 ?思路点拨

?代码详解  

⭐哈夫曼树-真题

?传送锚点

 ?思路点拨

?代码详解  


?哈夫曼树-模板

?题目描述

找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,

然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。

重复步骤1,直到{pi}中只剩下一个数。

在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。

本题任务

对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。

例如

对于数列{pi}={5, 3, 8, 2, 9},Huffman树的构造过程如下:

找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,

从{pi}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。

找到{5, 8, 9, 5}中最小的两个数,分别是5和5,

从{pi}中删除它们并将和10加入,得到{8, 9, 10},费用为10。

找到{8, 9, 10}中最小的两个数,分别是8和9,

从{pi}中删除它们并将和17加入,得到{10, 17},费用为17。

找到{10, 17}中最小的两个数,分别是10和17,

从{pi}中删除它们并将和27加入,得到{27},费用为27。

现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。

输入

输入的第一行包含一个正整数n(n< =100)。

接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。

输出

输出用这些数构造Huffman树的总费用。

?思路点拨

哈夫曼树模板很简单,只需要走5步:
1、先创建一个列表s,将树的结点从小到大排好序 s.sort()

2、从列表头出队两个结点 s.pop(0) s.pop(0)

3、累加两个结点的权值和 cnt+=s[0]+s[1] 

4、两个结点的权值和入队 s.append(s[0]+s[1])

5、再次从小到大排好序 s.sort()

?代码详解  

#哈夫曼树-模板
n=int(input())                  #5
s=list(map(int,input().split()))#[5, 3, 8, 2, 9]
s.sort()                        #[2, 3, 5, 8, 9]
cnt=0
for i in range(n-1):            #4次
    s.append(s[0]+s[1])         #[2, 3, 5, 8, 9, 17]
    cnt+=s[0]+s[1]              #17
    s.pop(0)                    #[3, 5, 8, 9, 17]
    s.pop(0)                    #[5, 8, 9, 17]
    s.sort()                    #[5, 8, 9, 17]
print(cnt)

'''
样例输入:
5
5 3 8 2 9

样例输出:
59
'''

⭐哈夫曼树-真题

?传送锚点

题目描述

小明买了 n 件白色的衣服,他觉得所有衣服都是一种颜色太单调,希望对这些衣服进行染色,每次染色时,他会将某种颜色的所有衣服寄去染色厂,第 i 件衣服的邮费为 a_i​ 元,染色厂会按照小明的要求将其中一部分衣服染成同一种任意的颜色,之后将衣服寄给小明, 请问小明要将 n 件衣服染成不同颜色的最小代价是多少?

输入描述

第一行为一个整数 n ,表示衣服的数量。

第二行包括 n 个整数 a_1, a_2 ... a_n a1​,a2​...an​ 表示第 i 件衣服的邮费为 a_i 元。

输出描述

输出一个整数表示小明所要花费的最小代价。

 ?思路点拨

上面的模板是靠列表list模拟队列来实现,新手容易理解,但速度较慢,考试时可能会超时。

所以下面换一种数据类型优先队列PriorityQueue,实现速度更快,考试直接满分!

它们的形式虽然不同,但原理是一样一样的(~ ̄▽ ̄)~

相信聪明的你,一看就懂!(๑•̀ㅂ•́)و✧

?代码详解  

#哈夫曼树-小明的衣服
from queue import PriorityQueue #优先队列
n=int(input())
a=list(map(int,input().split()))
q=PriorityQueue()          #创建数据结构
for i in a:
    q.put(i)               #入队
cnt=0
while q.qsize()!=1:        #队列还有2个数,不到1个数时
    a=q.get()              #出队
    b=q.get()              #出队
    cnt+=a+b               #权值累加
    q.put(a+b)             #入队
print(cnt)

'''
样例输入:
5
5 1 3 2 1

样例输出:
25
'''

  ​​​ 友友们,备战蓝桥最后14天,一起冲刺省赛一等奖!​​​

​​

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>