哈夫曼树

[编程题]哈夫曼树

热度指数：18137 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和的最小值。

输入描述:

输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出描述:

输出权值。

示例1

输入

5  
1 2 2 5 9

输出

算法知识视频讲解

鱼儿恋上水

发表于 2020-03-19 22:56:04

已知n个数，寻找一棵树，使得树的所有叶子结点的权值恰好为这n个数，并且使得这棵树的带权路径长度最小①树的带权路径长度=所有叶子结点的带权路径长度之和②带权路径长度=叶子结点的权值乘以其路径长度 #include <iostream> #include <cstdio> #in 展开全文

独特的布莱克在吵架

发表于 2023-02-23 10:46:19

#include <cstdio> #include <queue> using namespace std; int main(){ int n; scanf("%d",&n); priority_queue<int> que; 展开全文

牛客600247800号

发表于 2022-02-17 21:47:08

采用哈夫曼树的思想在机试中最常考察优先队列的应用便是哈夫曼树(Huffman Tree)。在一颗树中，从任意一个结点到达另一个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。如果树中结点带有表示某种意义的权值，那么从根结点到达该结点的带权路径长度再乘以该结点的权值就被称为该结点展开全文

yyer

发表于 2023-02-12 19:42:07

#include <queue> #include <iostream> using namespace std; int main() { int val,n,sum; while(scanf("%d",&n)!=EOF){ sum=0; 展开全文

帅呆呆～

发表于 2022-03-12 21:18:42

#include<iostream> #include<cstdio> #include<queue> using namespace std; int main() { int n; while(scanf("%d",&n) != EOF) { 展开全文

在考古的小鱼干很有气魄

发表于 2023-03-16 16:33:46

#include <bits/stdc++.h> using namespace std; int main(){ int n,tmp; vector<int> v; cin>>n; for(int i = 0; i < n; i++){ 展开全文

牛客774160366号

发表于 2023-06-25 17:34:06

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct Tnode { int value; struct Tnode* lchild; struct Tnod 展开全文

lyw菌

发表于 2023-03-01 15:44:39

//所有中间节点的权值和为带权路径长度，这个知识点很重要。剩余的就是利用小根堆（优先队列）了 #include "stdio.h" #include "queue" using namespace std; struct TreeNode{ int weight; }; bool oper 展开全文