文档章节

堆和树的区别

datacube
 datacube
发布于 2016/08/05 18:30
字数 934
阅读 352
收藏 1

以小根堆为例,堆的特点是双亲结点的关键字必然小于等于孩子结点的关键字,而两个孩子结点的关键字没有次序规定
而二叉排序树中,每个双亲结点的关键字均大于左子树结点的关键字,均小于右子树j结点的关键字,也就是说,每个双亲结点的左右孩子的关键字有次序关系
这样,当对两种树执行中序遍历后,二叉排序树会得到一个有序的序列,而堆不一定。


堆是一种特殊的树,它每个结点都有一个值,堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。就类似一堆东西一样,按照由大到小(或由小到大)“堆”起来。


堆是一种逻辑结构,树是一种存储结构,两者是不同层面的东西,就像“中国人"和“成年人”,本来就不矛盾。
heap一词反映了一种上小下大的金字塔状特征。


heap和tree结合,生了个孩子叫treap
中文名叫树堆。
首先它每个节点有2个值value和weight
其中只看weight的话,满足heap二叉堆的特性(父亲比儿子都小/大),只看value的话,满足排序二叉树特性(以左儿子为根的子树元素都比父亲小,右儿子为根的子树都比父亲大)
value是要维护的值,weight是随机生成的值。由于随机生成的堆使整棵treap变得平衡(严格证明请谷歌百度~),所以treap是一种比较短小精悍的平衡树的实现~

废话结束,回归题目(莫名押韵)
只要无环无向联通图都叫树,具体就是n个点n-1条无向边连接且任意两点联通的一种拓扑结构
如果我们选定一个节点作为根,那么这棵树就是有根树,遍历一遍就可以确定所有的父亲-儿子的关系了。。。
如果一棵有根树的每一个结点至多有两个儿子,那么这棵树称为二叉树

如果一棵二叉树的每一个节点都带着一个值,且父亲的值总是比儿子的值要大,我们称这棵树为大顶二叉堆,如果是父亲比儿子都要小,那就是小顶二叉堆,统称为二叉堆。(其实一般都把二叉两个字省略掉,毕竟通常说的堆都是二叉堆,然而堆不止二叉堆)。这一个良好的性质注定了堆可以用来当作优先队列使用。
优先队列支持以下操作
1.放一个元素进去
2.总是能取出一个最大的元素出来(大,小的规矩可以通过一个比较函数来定义)

显然堆就是可以这么做。

当然啦,之前说过堆不止二叉堆,还有更复杂的二项堆,斐波那契堆,配对堆等等。。。具体可查阅论文or算法导论

总结,堆是一种特殊的树。(结尾点题!)


堆的定义:在1到n/2的元素中,有k(i)<=k(2i),k(i)<=k(2i+1)
* 或k(i)>=k(2i),k(i)>=k(2i+1)
* 简单来说:就是假如将此序列看成一棵完全二叉树,要使这个无序列表
* 变成堆,则小于等于n/2(最后一个非终端节点就是n/2)的某个节点i的左右子节点均大于此节点
* 即堆的定义k(i)<=k(2i),k(i)<=k(2i+1)

本文转载自:http://www.zhihu.com/question/36134980/answer/66080662

上一篇: 选择排序
下一篇: 冒泡排序
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
基础算法应用场景浅析(2)

堆排序 在我们了解堆排序之前我们需要知道一个概念:树 用简单一点的概念来解释就是:不包含回路的连通无向图。~~解释可能有点生硬,还是用图说话... 例1 上图中左边的是一颗树 右边是一个图...

bf21189c27f6
2017/10/31
0
0
前端你应该了解的数据结构与算法

提到数据结构与算法都感觉这应该是后端要掌握的知识,对前端来说只要写写页面,绑定事件,向后台发发数据就好了,用不到数据结构与算法,也许对于一些数据查找 简单的for循环就能搞定,也许只...

幸福拾荒者
2018/06/29
0
0
花时间分别实现了AVL,SBT,Treap,RBT,还是有些收获的

发现AVL(平衡二叉树)和SBT(据说是国内某天才少年创造的宽度平衡二叉树),在数学上和树的构成上是完全等价的,SBT完全可以说是AVL的变种,创新之处在于使用统计(宽度)代替了高度,因此可...

刘地
2012/10/12
581
4
【从蛋壳到满天飞】JS 数据结构解析和算法实现-堆和优先队列(一)

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
03/26
0
0
常用数据结构以及数据结构的排序算法

数组 (Array)   在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可...

带梦想一7飞
2012/09/13
124
0

没有更多内容

加载失败,请刷新页面

加载更多

Java FOR-EACH循环

FOR-EACH循环使得代码更加的简短,也让代码更加易懂,其实他并没有加入什么新的功能。他的功能完全可以用简单的FOR循环代替。 for-each的用法: int a[] = {1,2,3,4,5,6} for(int s:a){ Syst...

无名氏的程序员
27分钟前
3
0
使用HTML5的History API

本文转载于:专业的前端网站➣使用HTML5的History API   HTML5 History API提供了一种功能,能让开发人员在不刷新整个页面的情况下修改站点的URL。这个功能很有用,例如通过一段JavaScript代...

前端老手
30分钟前
4
0
JAVA 编写redisUtils工具类,防止高并发获取缓存出现并发问题

import lombok.extern.slf4j.Slf4j;import org.springframework.data.redis.core.BoundHashOperations;import org.springframework.data.redis.core.BoundValueOperations;import org.......

huangkejie
今天
7
0
JMM内存模型(一)&volatile关键字的可见性

在说这个之前,我想先说一下计算机的内存模型: CPU在执行的时候,肯定要有数据,而数据在内存中放着呢,这里的内存就是计算机的物理内存,刚开始还好,但是随着技术的发展,CPU处理的速度越...

走向人生巅峰的大路
今天
101
0
你对AJAX认知有多少(2)?

接着昨日内容,我们几天继续探讨ajax的相关知识点 提到ajax下面几个问题又是必须要了解的啦~~~ 8、在浏览器端如何得到服务器端响应的XML数据。 通过XMLHttpRequest对象的responseXMl属性 9、 ...

理性思考
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部