前端编程算法之什么是二叉堆

来源:程序思维浏览:1203次
二叉堆是一种应用很广的数据结构,今天,我们就来简单讲讲二叉堆。

什么是二叉堆?

二叉堆是一种特殊的堆。具有如下的特性:
  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。

下面是构建代码的实现:

public class BinaryHeap {

   /**上浮操作,对插入的节点进行上浮
    *
    * @param arr
    * @param length :表示二叉堆的长度
    */
   public static int[] upAdjust(int arr[], int length){
       //标记插入的节点
       int child = length - 1;
       //其父亲节点
       int parent = (child - 1)/2;
       //把插入的节点临时保存起来
       int temp = arr[child];

       //进行上浮
       while (child > 0 && temp < arr[parent]) {
           //其实不用进行每次都进行交换,单向赋值就可以了
           //当temp找到正确的位置之后,我们再把temp的值赋给这个节点
           arr[child] = arr[parent];
           child = parent;
           parent = (child - 1) / 2;
       }
       //退出循环代表找到正确的位置
       arr[child] = temp;
       return arr;
   }

   /**

    */

   /**
    *  下沉操作,执行删除操作相当于把最后
    *  * 一个元素赋给根元素之后,然后对根元素执行下沉操作
    * @param arr
    * @param parent 要下沉元素的下标
    * @param length 数组长度
    */
   public static int[] downAdjust(int[] arr, int parent, int length) {
       //临时保证要下沉的元素
       int temp = arr[parent];
       //定位左孩子节点位置
       int child = 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;
       return arr;
   }

   /**
    * 构建操作
    *
    * @param arr
    */
   public static int[] buildHead(int[] arr,int length) {
       //从最后一个非叶子节点开始下沉
       for (int i = (length - 2) / 2; i >= 0; i--) {
           arr = downAdjust(arr, i, length);
       }
       return arr;
   }
}
精品好课
HTML5基础入门视频教程易学必会
HTML5基础入门视频教程,教学思路清晰,简单易学必会。适合人群:创业者,只要会打字,对互联网编程感兴趣都可以学。课程概述:该课程主要讲解HTML(学习HTML5的必备基础语言)、CSS3、Javascript(学习...
最新完整React+VUE视频教程从入门到精,企业级实战项目
React和VUE是目前最火的前端框架,就业薪资很高,本课程教您如何快速学会React和VUE并应用到实战,教你如何解决内存泄漏,常用库的使用,自己封装组件,正式上线白屏问题,性能优化等。对正在工作当中或打算学习Re...
VUE2+VUE3视频教程从入门到精通(全网最全的Vue课程)
VUE是目前最火的前端框架之一,就业薪资很高,本课程教您如何快速学会VUE+ES6并应用到实战,教你如何解决内存泄漏,常用UI库的使用,自己封装组件,正式上线白屏问题,性能优化等。对正在工作当中或打算学习VUE高薪就...
jQuery视频教程从入门到精通
jquery视频教程从入门到精通,课程主要包含:jquery选择器、jquery事件、jquery文档操作、动画、Ajax、jquery插件的制作、jquery下拉无限加载插件的制作等等......
最新完整React视频教程从入门到精通纯干货纯实战
React是目前最火的前端框架,就业薪资很高,本课程教您如何快速学会React并应用到实战,教你如何解决内存泄漏,常用UI库的使用,自己封装组件,正式上线白屏问题,性能优化等。对正在工作当中或打算学习React高薪就...
Vue2+Vue3+ES6+TS+Uni-app开发微信小程序从入门到实战视频教程
2021年最新Vue2+Vue3+ES6+TypeScript和uni-app开发微信小程序从入门到实战视频教程,本课程教你如何快速学会VUE和uni-app并应用到实战,教你如何解决内存泄漏,常用UI库的使用,自己...
HTML5视频播放器video开发教程
适用人群1、有html基础2、有css基础3、有javascript基础课程概述手把手教你如何开发属于自己的HTML5视频播放器,利用mp4转成m3u8格式的视频,并在移动端和PC端进行播放支持m3u8直播格式,兼容...
React实战视频教程仿京东移动端电商
React是前端最火的框架之一,就业薪资很高,本课程教您如何快速学会React并应用到实战,对正在工作当中或打算学习React高薪就业的你来说,那么这门课程便是你手中的葵花宝典。
收藏
扫一扫关注我们