堆和树的区别 |
您所在的位置:网站首页 › 女排一队和二队的区别是什么呢 › 堆和树的区别 |
来一个离题的开头: heap和tree结合,生了个孩子叫treap。中文名叫树堆。 首先它每个节点有2个值value和weight 其中只看weight的话,满足heap二叉堆的特性(父亲比儿子都小/大),只看value的话,满足排序二叉树特性(以左儿子为根的子树元素都比父亲小,右儿子为根的子树都比父亲大) value是要维护的值,weight是随机生成的值。由于随机生成的堆使整棵treap变得平衡(严格证明请谷歌百度~),所以treap是一种比较短小精悍的平衡树的实现~ 只要无环无向联通图都叫树,具体就是n个点n-1条无向边连接且任意两点联通的一种拓扑结构 如果我们选定一个节点作为根,那么这棵树就是有根树,遍历一遍就可以确定所有的父亲-儿子的关系了。。。 如果一棵有根树的每一个结点至多有两个儿子,那么这棵树称为二叉树 如果一棵二叉树的每一个节点都带着一个值,且父亲的值总是比儿子的值要大,我们称这棵树为大顶二叉堆,如果是父亲比儿子都要小,那就是小顶二叉堆,统称为二叉堆。(其实一般都把二叉两个字省略掉,毕竟通常说的堆都是二叉堆,然而堆不止二叉堆)。 这一个良好的性质注定了堆可以用来当作优先队列使用。 优先队列支持以下操作: 放一个元素进去总是能取出一个最大的元素出来(大,小的规矩可以通过一个比较函数来定义)显然堆就是可以这么做。 堆不止二叉堆,还有更复杂的二项堆,斐波那契堆,配对堆等等。。。 总结,堆是一种特殊的树。
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |