精华内容
下载资源
问答
  • 描述众所周知,合并果子是堆的入门题,而 合并果子就是构造哈夫曼树。现在问题就是,在给定有序的数组aa下,如何O(n)O(n)构造哈夫曼树。算法使用两个队列,从小到大将数组aa的元素加入队列firfir,队列secsec为空。...

    描述

    众所周知,合并果子是堆的入门题,而 合并果子就是构造哈夫曼树。现在问题就是,在给定有序的数组a下,如何O(n)构造哈夫曼树。

    算法

    使用两个队列,从小到大将数组a的元素加入队列fir,队列sec为空。

    每次我们将两个元素合并,可以证明一定是三种之一。

    1. 队列fir中的队首和第二位合并
    2. 队列sec中的队首和第二位合并
    3. 队列fir中的队首和sec中的队首合并

    优先考虑合并的两个数的和较小的情况。

    将每次合并完的数放入sec队列,直到sec队列只有一个元素,结束算法。

    展开全文
  • 输入样例: 8 4 5 1 2 1 3 1 1 输出样例: 49 题目目的是让花费最少,而这个花费就是每次切的长度之和,而哈夫曼树是带权路径最短的树,而权正好相当于切后两块木板长度和,所以费用就是哈夫曼树中所有权之和,所以用...

    题目如下:
    农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数L​i个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是L​i 的总和。
    但是农夫自己没有锯子,请人锯木的酬金跟这段木头的长度成正比。为简单起见,不妨就设酬金等于所锯木头的长度。例如,要将长度为20的木头锯成长度为8、7和5的三段,第一次锯木头花费20,将木头锯成12和8;第二次锯木头花费12,将长度为12的木头锯成7和5,总花费为32。如果第一次将木头锯成15和5,则第二次锯木头花费15,总花费为35(大于32)。
    请编写程序帮助农夫计算将木头锯成N块的最少花费。
    输入格式:
    输入首先给出正整数N(≤104),表示要将木头锯成N块。第二行给出N个正整数(≤50),表示每段木块的长度。
    输出格式:
    输出一个整数,即将木头锯成N块的最少花费。
    输入样例:
    8
    4 5 1 2 1 3 1 1
    输出样例:
    49

    题目目的是让花费最少,而这个花费就是每次切的长度之和,而哈夫曼树是带权路径最短的树,而权正好相当于切后两块木板长度和,所以费用就是哈夫曼树中所有权之和,所以用需要的木板长度构建哈夫曼树,再求权和即可。

    用stl中的vector容器代替树:

    #include<bits/stdc++.h>
    using namespace std;
    #define maxlen 10000000
    int main()
    {
    	int n,a;
    	cin >> n;
    	vector<int>v;
    	while (n--)
    	{
    		cin >> a;
    		v.push_back(a);
    	}
    	int sum = 0;
    	for (;;)  //projectA代码
    	{
    		vector<int>::iterator x = min_element(v.begin(), v.end());
    		int temp1 = *x;
    		*x = maxlen;
    		vector<int>::iterator y = min_element(v.begin(), v.end());
    		if (*y == (maxlen))
    			break;
    		int temp2=*y;
    		*y = maxlen;
    		sum += temp1 + temp2;
    		v.push_back(temp1 + temp2);
    		//*y = maxlen;
    	}
    	/*	projectB代码
    	while (v.size() != 1)
    	{
    		vector<int>::iterator x = min_element(v.begin(), v.end());
    		int a = *x;
    		v.erase(x);
    		vector<int>::iterator y = min_element(v.begin(), v.end());
    		int b = *y;
    		v.erase(y);
    		sum += a+b;
    		v.push_back(a+b);
    	}*/
    	cout << sum;
    	return 0;
    }
    

    代码中第27行的*y = maxlen不能写在这个位置,只能写在第24行,因为上一行对vector进行了操作,一旦对容器操作后,之前定义的迭代器就不能再使用了,会出现 vector iterator not dereferencable 的迭代器越界,这个耽误了我很久。
    代码中29行–40行的projectB代码可以替代15行–28行projectA代码,但是vector容器是类似数组的顺序类容器,所以进行在非尾部进行增删操作时实际上会耗时较多,所以projectB中的erase函数会影响时间复杂度,而projectA中采用将使用过的元素(子节点)置为足够大的数,再用条件语句跳出循环,按理说能够更快的完成任务。但是erase函数和remove函数不同,erase函数会减少vector的长度,remove函数则是移开删除元素,不会减少长度,而两个方法中都有min_element函数,这个函数的执行时间也与vector的长度有关,时间复杂度应该O(n),所以在这里projectB又更优了,经过测试,在n即需求木板数较少时,projectA更优,而在较大时,projectB更优,以下分别是两个计划的通过时间projectA
    projectB

    展开全文
  • 本文将提到在牛客网刷题中遇到的各类知识点:线性表的概念、哈夫曼树时间复杂度等多方面知识点并赋实际题目。 目录 阅读提示 1、线性表概念 2、 哈夫曼树 3、前序遍历、中序遍历、后序遍历 4、题: 删除指针节点...

    阅读提示

    本文将提到在牛客网刷题中遇到的各类知识点:线性表的概念、哈夫曼树、时间复杂度等多方面知识点并赋实际题目。

    1、线性表概念

    • 对于同一个线性表,其每一个数据元素的值虽然不同,但必须具有相同的数据类型;

    • 数据元素之间具有一种线性的或“一对一”的逻辑关系。

    1. 第一个数据元素没有前驱,这个数据元素被称为开始节点;
    2. 最后一个数据元素没有后继,这个数据元素被称为终端节点;
    3. 除了第一个和最后一个数据元素外,其他数据元素有且仅有一个前驱和一个后继。

    考题:线性表的链表易于插入/删除,顺序表易于寻址

    2、 哈夫曼树

    ​    赫夫曼树,别名“哈夫曼树”、“最优树”以及“最优二叉树”。

    路径: 在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。

    路径长度: 在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

    结点的权: 给每一个结点赋予一个新的数值,被称为这个结点的权。例如,图 1 中结点 a 的权为 7,结点 b 的权为 5。

    结点的带权路径长度: 指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

       树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为:

    ​                            WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

    在这里插入图片描述)

    什么是哈夫曼树?

       当用n个节点都做叶子结点,且都有各自的权值)构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为 “最优二叉树” ,有时候也叫赫夫曼树或者哈夫曼树

       在构建哈夫曼树的时候,为了使带权路径最小应遵循一个原则:

    ​    权重越大的节点离根节点越近,如上图,a的权重最大 ,故a离根节点最近,理应作为根节点的孩子节点。

    构建哈夫曼树

    在n个权值中选择两个最小的权值,构成一个新的二叉树

    也就是说:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
       直到所有节点都构成了一个新的二叉树,这就是哈夫曼树。

    考题: 赫夫曼(huffman)树,在赫夫曼树中, 每次从候选集中选择最小的两个元素构建新的根节点,所以只存在度为0和2的节点,结点的度数只可能为0、2

    3、前序遍历、中序遍历、后序遍历

    前序遍历:根左右

    中序遍历:左根右

    后序遍历:左右根

    eg:

    前序:HGEDBFCA

    中序:EGBDHFAC

    分析:

    1.由前序遍历知,H为根节点。

    2.在中序遍历中,EGBD为左子树,FAC为右子树,对比前序遍历可得G和F作为第二层的根节点

    3.将G,F作为根节点,看中序遍历,E为G的左节点,BD为右节点,在前序遍历中,D先于B,故D右节点,将D作为根节点,B的中序遍历在D的左边,故为左节点

    4.右侧同理

    总结:

    前序遍历的第一个是整个树的根;

    后序遍历的最后一个是整个树的根;

    中序是用来判别左右子树划分的;

    前序序列中左子树部分的第一个节点是左子树的根节点 ;

    前序序列中右子树部分的第一个节点是右子树的根节点 ;

    4、题: 删除指针节点

    ​    双向链表中有两个指针域,llink和rlink分别指向前驱和后继,设p指向链表中的一个结点,现要求删去p所指结点,则正确的删除是()(链中结点数大于2,p不是第一个结点)

    答:

    首先要更新p结点前后结点的指针域,然后删除P,所以做法是:

    p -> link -> rlink = p -> rlink;

    p -> rlink -> link = p -> link;

    dispose§;

    5、题: 武器暴击概率题

    一个英雄基础攻击力为100,携带了三件暴击武器,武器A有40%的概率打出2倍攻击,武器B有20%的概率打出4倍攻击,武器C有10%概率打出6倍攻击,各暴击效果触发是独立事件,但是多个暴击效果在一次攻击中同时触发时只有后面武器的暴击真正生效,例如一次攻击中武器A判定不暴击,武器B和武器C都判定触发暴击,那么这次攻击实际是600攻击力。那么这个英雄攻击力的数学期望是____。

    答:

    也就是说 使用武器3的时候: 600 * 10%

    ​ 使用武器2的时候,要确保不使用武器3: 400 * (1-10%) * 20%

    ​ 使用武器1的时候,要确保不适用武器13 : 200 * (1-10%) * (1-20%)

    ​ 不使用武器的时候:100 * (1-10%) * (1-20%) * (1-40%)

    所以 总的数学期望为: (600 * 10%) +(400 * 90% * 20% )+(200 * 90% * 80% * 40%) +(100 * 60 % * 80% * 90%)= 232.8

    6、题:能否构成折半查找

    下列选项中,不能构成折半查找中关键字比较序列的是____

    500,200,450,180

    500,450,200,180

    180,500,200,450

    180,200,500,450

    答:

    二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

    (1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;

    (2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;

    (3)左、右子树也分别为二叉排序树;

    通俗来讲: 那就是前一个元素要么大于后面每一个元素,要么小于后面每一个元素

    7、基数排序问题

    对[21, 49, 84, 45, 12]进行基数排序,第一趟排序的结果为 ___

    答:

    对10取余 进行排序 即按照个位数的大小进行排序

    也就是

    21,12,84,45,49

    8、时间复杂度问题

       排序时,若不采用计数排序的等空间换时间的方法,合并m个长度为n的已排序数组的时间复杂度最优为___

    答:

    当n=1时,就成了m个数的归并排序,时间复杂度为O(mlogm)

    9、二叉链表存储问题

    利用二叉链表存储树,则根结点的右指针是___

    答:

    二叉链表: 孩子 兄弟

    由于根节点没有兄弟 所以为空

    展开全文
  • 时间复杂度(一)

    2018-08-25 16:15:41
    二叉查找树——时间复杂度logN(N总数) 高度初值1 深度初值0   AVL高度平衡树 红黑树插入N个——时间复杂度NlogN 哈夫曼树,权值大的靠近根。应用于变长编码表中...

    二叉查找树——时间复杂度logN(N总数)

    • 高度初值1
    • 深度初值0

     

    AVL高度平衡树

    红黑树插入N个——时间复杂度NlogN

    哈夫曼树,权值大的靠近根。应用于变长编码表中

    展开全文
  • 哈夫曼树的建立

    千次阅读 2019-01-05 20:34:25
    3.分析算法的时间复杂度,进行优化。 三、设计报告的内容 1.设计题目与设计任务 设计题目:建立赫夫曼。 设计任务:建立最优二叉树函数,并输出其赫夫曼。实现赫夫曼存储结构的初始化,建立赫夫曼并...
  • 西电复试之——真题2011D 哈夫曼树 1 优先队列 //基础知识 priority_queue<int> q; //push()时间复杂度O(logN) q.push(3); //优先队列没有front()函数和back()函数(队列中队首队尾),只能用top()访问队首...
  • 问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即...
  • 题意:给一个长度为n的数列a,q组询问,每组询问求将li到ri的区间中的数哈夫曼编码的长度。莫队,对于每一个询问处理该区间内出现次数为x的字符个数。 对于次数小于n√\sqrt{n} 的字符,...时间复杂度O(nn√logn)O(n
  • 【树】哈夫曼树(一)

    2016-12-09 19:39:49
    用二进制数表示这n个字母的编码方案.(左子树根节点的权小于等于右子根节点的权,按中序遍历输出)思路此题时间复杂度为O(N^2)。在序列中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子构造一棵新的...
  • 二叉查找比普通查找更快,查找、插入、删除的时间复杂度为O(logN)。但是二叉查找有一种极端的情况,就是会变成一种线性链表似的结构。此时时间复杂度就变味了O(N),为了解决这种情况,出现了二叉平衡。 ...
  • 其实基本是基于C的代码实现的,时间复杂度还可以,变量比较多,但思路很清晰。
  • # 求大佬看下这段代码的时间复杂度和空间复杂度,一直不太会算这个 ``` #include typedef struct { double weight; int parent; int lchild, rchild; }Node; typedef struct { int node[12]; int ...
  • 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子...
  • Java数据结构与算法_09 树结构实际应用堆排序完整代码哈夫曼树(Huffman Tree)完整代码哈夫曼编码(Huffman Coding) 本人是个新手,写下博客用于自我复习、自我总结。 如有错误之处,请各位大佬指出。 学习资料来源于...
  • 「一本正经的聊数据结构(1):时间复杂度」 「一本正经的聊数据结构(2):数组与向量」 「一本正经的聊数据结构(3):栈和队列」 「一本正经的聊数据结构(4):」 「一本正经的聊数据结构(5):二叉树的存储...
  • 什么是堆? 堆是按照一定顺序组织的完全二叉树 ...可以,查找与删除的时间复杂度均为以2为底n的对数即log(2)n 二叉搜索? 如果采用二叉树结构,应更关注插入还是删除?(删除)  结点顺序怎么...
  • 2、哈夫曼树、平衡二叉树都是数据的逻辑结构() 正确答案: A 你的答案: B (错误) 对 错 解析:线性表,树,图 这些都是对数据逻辑结构的描述。 数据的存储结构只有顺序结构和链式结构(不一定是单链 3、有n个节点的...
  • 我们知道堆的插入、删除操作的时间复杂度都是 O(logN)O(logN),自然优先队列的插入、删除操作的时间复杂度也都是 O(logN)O(logN)。堆中的堆顶元素就是优先队列的队首元素。对于大根堆实现的优先队列,总是优先级高的...
  • 时间复杂度 空间复杂度 说明 Hanoi $ O(2^n) $ $ O(n) $ 递归使用 会场安排问题 \(O(nlogn)\) \(O(n)\) 贪心 哈夫曼树编码 \(O(nlogn)\) \[O(n)\] 贪心 \[O(n^2) \](未采用特殊数据结构) dijkstra \(O(n...
  • 努力把它的时间复杂度变成了线性。 首先怎么生成一棵哈夫曼树(人工运算)我们是知道的吧。 计算机上。 我的做法分成了3步,准确说是4步。去生成一棵哈夫曼树,其复杂度控制在O(n) 然后我用哈夫曼树去进行编码其...
  • 5.哈夫曼编码

    千次阅读 2020-04-07 21:49:33
    哈夫曼编码1.哈夫曼编码的原理2....在算法导论中,哈夫曼编码使用优先队列管理结点序列,如果优先队列使用最小堆来维护,这样哈夫曼编码算法时间复杂度为O(n*lgn); 哈夫曼编码主要用于数据压缩,...
  • 1.题目 哈夫曼树的应用 要传输一则报文内容如下: “AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF” 请为这段报文设计哈夫曼编码...请分析算法的效率,至少包括时间复杂度和空间复杂度等。 2.分析
  • 哈夫曼编码详解(C语言实现)

    万次阅读 多人点赞 2018-12-21 21:28:43
    解决问题的方法:我们可以通过构建哈夫曼树来得到哈夫曼编码。 关于算法我们可以从如下几部分分析:算法的逻辑结构、算法的存储结构、以及算法本身考虑,同时也需要考虑时间和空间的复杂度,关于哈夫曼编码,我们...
  • 数据结构——哈夫曼编/译码器

    千次阅读 2019-02-01 12:36:38
    在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息...
  • 1. 该程序可对不含中文字符的...其中创建Huffman时间复杂度被优化为O(nlog2n),编码中根据字符查询对应的编码的时间复杂度被优化为O(log2n) 4. 使用C++编写。 5. 模块之间低耦合,便于维护,代码可重用性高。
  • 对于给定的文档,首先通过扫描确定文档中出现了哪些英文字母以及出现的次数,以出现的次数作为叶子结点的权值构造哈夫曼树,获得各字符的哈夫曼编码;然后再扫描一遍文档将其进行哈夫曼压缩编码,将文本文档转换为二...
  • 在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息...
  • 是时候提升一下自己的内功了,数据结构与算法还是非常有必要要学习一下的,仅开此栏单单为了记录自己学习数据结构 的学习进程喝进度,目标是三个月左右的时间,从链表到哈夫曼树全部掌握,已经对应的leetcode上对应...
  • 「一本正经的聊数据结构(1):时间复杂度」 「一本正经的聊数据结构(2):数组与向量」 「一本正经的聊数据结构(3):栈和队列」 「一本正经的聊数据结构(4):」 「一本正经的聊数据结构(5):二叉树的存储...

空空如也

空空如也

1 2 3 4 5
收藏数 88
精华内容 35
关键字:

哈夫曼树时间复杂度