词条信息

admin
admin
超级管理员
词条创建者 发短消息   

相关词条

热门词条

更多>>
什么是端口?到底是做什么的呢?
端口一般指两种,一种是硬件比如路由器或者交换机的插网线的端口,一种是软件的逻辑的概念,比如http的80端口!...
7种进阶方法让你快速测试端口连通性
Ping是Windows、Linux和Unix系统下的一个检查网络连通性的命令工具,对于大部分互联网用户来说很...
电脑开机,总需要按F1,是什么原因造成的?
一.主板掉电这个说法是行业内的叫法了,一般是主板的CMOS电池没电了导致的。也是最常见的一种提示你按F1的提示...
社保降费对个人有什么影响?
下调城镇职工基本养老保险单位缴费比例是政府给企业发的一个大红包,特别是对于企业来说是一个利好,但是对个人来说有...
车辆“出险”对下年保费的影响,到底有多大?
【出险对交强险的影响】【出险对商业险的影响】车辆“出险”对下年保费的影响,到底有多大?这里有必要先提下车险第三...

精选图集

更多>>
简易百科旧版 >>所属分类 >> 程序开发    数据结构   

什么是二叉堆?

标签: 二叉堆 数据结构

顶[0] 发表评论(0) 编辑词条

二叉堆是一种应用很广的数据结构,今天,我们就来简单讲讲二叉堆。


目录

什么是二叉堆?编辑本段回目录


二叉堆是一种特殊的堆。具有如下的特性:

  1. 具有完全二叉树的特性。
  2. 堆中的任何一个父节点的值都大于等于它左右孩子节点的值,或者都小于等于它左右孩子节点的值。

根据第二条特性,我们又可以把二叉堆分成两类:


1、最大堆:父节点的值大于等于左右孩子节点的值。


2、最小堆:父节点的值小于等于左右孩子节点的值。

我们把二叉堆的根节点称之为堆顶。根据二叉堆的特性,堆顶要嘛是整个堆中的最大元素,要嘛是最小元素

今天,我们主要来讲讲二叉堆的三个主要操作:

  1. 插入一个节点。
  2. 删除一个节点。
  3. 构建一个二叉堆。

不过这里需要注意的是,在二叉堆这种结构中,对于删除一个节点,我们一般删的是根节点


下面我们以最小堆为例子,来讲讲这些操作。


插入一个节点。编辑本段回目录


刚才我们说二叉堆具有完全二叉树的特性,因此,我们在插入一个节点的时候,应该先保证节点插入后,它仍然是一颗完全二叉树,然后再来进行调整,使它满足二叉堆的另一个特性。

所以,在插入的时候,我们把新节点插到完全二叉树的最后一个位置。例如:

插入0。

之后我们再来进行调整,调整的原则是:让新插入的节点与它的父节点进行比较,如果新节点小于父节点,则让新节点上浮,即和父节点交换位置。

上浮之后继续和它的父节点进行比较,直到父节点的值小于或等于该节点,才停止上浮,即插入结束。例如:

0比5小,上浮。

0比2小于,上浮。

0比1小,上浮。

已经到达堆顶了,插入结束。

删除节点。编辑本段回目录


前面说了,删除节点一般删除的是根节点。


和插入一样,由于二叉堆具有完全二叉树的特性,因为删除时候,首先我们是要马上恢复它具有完全二叉树的特性,所以我们是采取这样的策略:把根节点删除之后,用二叉堆的最后一个元素顶替上来,然后在进行调整恢复。例如:

把0删除了之后,5替换上来。

之后再来调整,调整的规则和插入差不多类似,采取下沉的策略:让5和左右孩子节点相比较,如果左右节点有小于5的,则让那个较小的孩子代替5的位置,然后5下沉。

下沉之后,5继续和左右孩子相比,直到左右孩子都大于或等于5才结束。

如:5比1,3都大,1代替5的位置

5比4,2都大,2代替5的位置。

5已经不在具有左右孩子了,删除结束。


构建二叉堆编辑本段回目录


所谓构建,就是给你一个有n个节点的无序的完全二叉树,然后把它构建成二叉堆。


刚才我们在删除一个节点的时候,把最后一个元素补到根元素的位置上去,然后再让这个元素依次下沉,实际上,在这个元素还没有下沉之前,它就可以看作是一颗无序的完全二叉树了


也就是说,要把一个无序的完全二叉树调整为二叉堆,我们可以让所有非叶子节点依次下沉。不过下沉的顺序不是从根节点开始下沉(想一下相必你就 知道不能从根节点开始下沉),而是从下面的非叶子节点下称,在依次往上。举个例子:


对于这样一颗无序的完全二叉树


8进行下沉。

接着,5进行下沉。

2没问题,之后让7进行下沉

调整完成,构建结束。


代码实现

不过这里需要说明的是,我们二叉树一般是采用链表的方式来实现的,但二叉堆我们是采用数组的方式来存储的。


如果知道了一个节点的位置,如何知道一个节点的左右孩子节点的位置呢?


这其实不难,根据完全二叉树的特点,假如一个节点的下标为n,则可以求得它左孩子的下标为:2 n+1;右孩子下标为:2 n+2。


下面是构建代码的实现:


publicclassBinaryHeap{

/**上浮操作,对插入的节点进行上浮

*

* @param arr

* @param length :表示二叉堆的长度

*/

publicstaticint[] upAdjust(intarr[], intlength){

//标记插入的节点

intchild = length - 1;

//其父亲节点

intparent = (child - 1)/ 2;

//把插入的节点临时保存起来

inttemp = arr[child];

//进行上浮

while(child > 0&& temp < arr[parent]) {

//其实不用进行每次都进行交换,单向赋值就可以了

//当temp找到正确的位置之后,我们再把temp的值赋给这个节点

arr[child] = arr[parent];

child = parent;

parent = (child - 1) / 2;

}

//退出循环代表找到正确的位置

arr[child] = temp;

returnarr;

}

/**

*/

/**

* 下沉操作,执行删除操作相当于把最后

* * 一个元素赋给根元素之后,然后对根元素执行下沉操作

* @param arr

* @param parent 要下沉元素的下标

* @param length 数组长度

*/

publicstaticint[] downAdjust(int[] arr, intparent, intlength) {

//临时保证要下沉的元素

inttemp = arr[parent];

//定位左孩子节点位置

intchild = 2* parent + 1;

//开始下沉

while(child < length) {

//如果右孩子节点比左孩子小,则定位到右孩子

if(child + 1< length && arr[child] > arr[child + 1]) {

child++;

}

//如果父节点比孩子节点小或等于,则下沉结束

if(temp <= arr[child])

break;

//单向赋值

arr[parent] = arr[child];

parent = child;

child = 2* parent + 1;

}

arr[parent] = temp;

returnarr;

}

/**

* 构建操作

*

* @param arr

*/

publicstaticint[] buildHead(int[] arr,intlength) {

//从最后一个非叶子节点开始下沉

for( inti = (length - 2) / 2; i >= 0; i--) {

arr = downAdjust(arr, i, length);

}

returnarr;

}

}


本次讲解到此结束。下篇继续讲解和堆有关的知识点。至于bitmap算法优化的那篇,会在之后给出。


【本文作者】

帅地:一个热爱编程的在校生,我的世界不只有coding,还有writing。目前维护订阅号「苦逼的码农」,专注于写计算机网络,数据结构等相关文章。

 

 

附件列表


按字母顺序浏览:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

→我们致力于为广大网民解决所遇到的各种电脑技术问题
 如果您认为本词条还有待完善,请 编辑词条

上一篇算法有偏见么?
下一篇数据结构

0
1. 本站部分内容来自互联网,如有任何版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
2. 本站内容仅供参考,如果您需要解决具体问题,建议您咨询相关领域专业人士。
3. 如果您没有找到需要的百科词条,您可以到百科问答提问或创建词条,等待高手解答。

关于本词条的提问

查看全部/我要提问>>