文档章节

数据结构-堆

如比如比
 如比如比
发布于 2015/06/24 05:25
字数 1353
阅读 326
收藏 20

数据结构-堆

堆(英语:Heap),是一种拥有像树那样的特殊数据结构,或者理解为具有优先级的树。它的特点是父节点的值大于(或小于)两个子节点的值(分别称为大顶堆和小顶堆)。它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等。堆通常是一个可以被看做一棵树的数组(或ArrayList)对象。常见的堆有二叉堆、二项堆、斐波那契堆等。

 

二叉堆(Binary heap)

二叉堆是一种特殊的堆,实为二叉树的一种;是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

 

二项堆(Binomial heap)

二项堆是一种类似于二叉堆的堆结构。与二叉堆相比,其优势是可以快速合并两个堆,因此它属于可合并堆(mergeable heap)抽象数据类型的一种。

二项堆是指满足以下性质的二项树的集合:

每棵二项树都满足最小堆性质,即结点关键字大于等于其父结点的关键字

不能有两棵或以上的二项树有相同度数(包括度数为0)。换句话说,具有度数k的二项树有0个或1个。

以上第一个性质保证了二项树的根结点包含了最小的关键字。第二个性质则说明结点数为n的二项堆最多只有\log{n} + 1棵二项树。实际上,包含n个节点的二项堆的构成情况,由n的二进制表示唯一确定,其中每一位对应于一颗二项树。

 

二项树(Binomial trees)

二项树递归定义如下:

数为0的二项树只包含一个结点

度数为k的二项树有一个根结点,根结点下有k个子女,每个子女分别是度数分别为k-1, k-2, ..., 2, 1, 0的二项树的根

度数为k的二项树共有2^k个结点,高度为k。在深度d处有(n d)(二项式系数)个结点。

度数为k的二项树可以很容易从两颗度数为k-1的二项树合并得到:把一颗度数为k-1的二项树作为另一颗原度数为k-1的二项树的最左子树。这一性质是二项堆用于堆合并的基础。

 

斐波那契堆(Fibonacci heap)

斐波那契堆(Fibonacci heap)是树的集合。它比二项式堆具有更好的平摊分析性能,可用于实现合并优先队列。不涉及删除元素的操作有O(1)的平摊时间。 Extract-Min和Delete的数目和其它相比,较小时效率更佳。稠密图每次decrease key只要O(1)的平摊时间,和二项堆的O(lg n)相比是巨大的改进。

斐波纳契堆于1984年由Michael L. Fredman与Robert E. Tarjan提出,1987年公开发表。名字来源于运行时分析使用的斐波那契数。

斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。

斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针p[x]和指向任意一个子结点的child[x]。x的所有子节点都用双向循环链表链接起来,叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果节点y是x仅有的子节点,则left[y]=right[y]=y。

斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。

使用一个指针指向斐波那契堆中最小元素。

 

堆的基本操作

创建一个堆build

向堆中插入一个新元素、新节点insert

将新元素提升、降低使其符合堆的性质update

增加、减小节点的值、增加、减小关键字的值、提高、降低一个节点的键值decrease-key

获取当前堆顶元素的值get

查找最小(大)关键字所在节点、查找最小(大)的节点 Find minimum、Find maximum, find-min

使删除堆顶元素的堆再次成为堆heapify

删除(释放)最小(大)关键字所在节点 Delete minimum, delete-min

删除给定节点Delete

删除堆顶元素、根节点delete

合并两个堆merge

 

某些堆实现还支持其他的一些操作,如斐波那契堆支持检查一个堆中是否存在某个元素。

 

堆的应用

堆的最常见应用是堆排序,时间复杂度为O(N lg N)。如果是从小到大排序,用大顶堆;从大到小排序,用小顶堆。

 

© 著作权归作者所有

如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
堆和栈(Java数据结构)

堆 常见使用场景: (英语:heap)亦被称为: 优先队列 (英语:priority queue),是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反...

晓阳
2015/10/14
91
0
c#语法复习总结(2)-数据类型

C#数据类型可以分值类型和引用类型。值类型,先说说一个概念 c#栈和堆. 一,栈和堆. 堆:在c里面叫堆,在c#里面其实叫托管堆。为什么叫托管堆,我们往下看。 栈:就是堆栈,因为和堆一起叫着...

在神
05/06
0
0
关于PriorityQueue 二叉堆的问题

场景:最近在研究java中的队列,当研究到优先队列的时候去读 PriorityQueue的源码的时候发现一种数据结构,我数据结构这块基本上上是空白,所以让我晦涩难懂啊,于是我查阅了大量资料以及手动...

skyline520
2013/06/01
924
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-堆和优先队列(一)

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

哎哟迪奥
03/26
0
0
LeetCode题集整理- 栈、队列、堆

1、预备知识点 栈(Stack)和队列(Queue)是两种操作受限的线性表。 (线性表:线性表是一种线性结构,它是一个含有n≥0个结点的有限序列,同一个线性表中的数据元素数据类型相同并且满足“...

Blank_佐毅
2017/11/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

springboot 403 问题

添加WebAppConfigurer 配置 @Configuration@EnableAutoConfigurationpublic class WebAppConfigurer extends WebMvcConfigurerAdapter { public WebAppConfigurer() { } ......

布袋和尚_爱吃鱼
5分钟前
1
0
Python自动更换壁纸爬虫与tkinter结合

直接上代码 import ctypesimport timeimport requestsimport osfrom threading import Threadfrom tkinter import Tk, Label, Button,Entry,StringVar,messagebox# '放到AppData\Roami......

物种起源-达尔文
5分钟前
1
0
Postgresql Study 笔记

Postgresql 安装 Windows, MAC Install Postgresql 下载地址: https://www.enterprisedb.com/downloads/postgres-postgresql-downloads Linux Install sudo apt-get update sudo apt-get in......

slagga
7分钟前
1
0
layer.open 打开新页面传参问题

如图所示,点击出售,把A页面的数据传到弹框上面,因为弹框比较复杂,所以使用引入一个新页面。 A.html a.js B.html b.js 1、第一种方案 sellInte: function (){ var obj = document.g...

木九天
10分钟前
1
0
沙龙报名 | 区块链数据服务技术应用实践

京东云是国内首家提供区块链数据在线分析服务产品的公司,也是行业内首家对区块链数据服务进行开源的公司。 本次沙龙是京东云BDS开源后,首次在深圳举办线下沙龙,我们将邀请京东云BDS团队核...

京东云技术新知
11分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部