资讯专栏INFORMATION COLUMN

js数据结构-二叉树(二叉堆)

ningwang / 539人阅读

摘要:二叉树二叉树是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。

二叉树

二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。

根节点:二叉树最顶层的节点

分支节点:除了根节点以外且拥有叶子节点

叶子节点:除了自身,没有其他子节点

常用术语
在二叉树中,我们常常还会用父节点和子节点来描述,比如图中2为6和3的父节点,反之6和3是2子节点

二叉树的三个性质

在二叉树的第i层上,至多有2^i-1个节点

i=1时,只有一个根节点,2^(i-1) = 2^0 = 1

深度为k的二叉树至多有2^k-1个节点

i=2时,2^k-1 = 2^2 - 1 = 3个节点

对任何一棵二叉树T,如果总结点数为n0,度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要差别

树的节点个数至少为1,而二叉树的节点个数可以为0

树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2

树的节点没有左右之分,而二叉树的节点有左右之分

二叉树分类

二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

满二叉树:一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树

完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

二叉树的数组表示

用一个数组来表示二叉树的结构,将一组数组从根节点开始从上到下,从左到右依次填入到一棵完全二叉树中,如下图所示

通过上图我们可以分析得到数组表示的完全二叉树拥有以下几个性质:

left = index * 2 + 1,例如:根节点的下标为0,则左节点的值为下标array[0*2+1]=1

right = index * 2 + 2,例如:根节点的下标为0,则右节点的值为下标array[0*2+2]=2

序数 >= floor(N/2)都是叶子节点,例如:floor(9/2) = 4,则从下标4开始的值都为叶子节点

二叉堆

二叉堆由一棵完全二叉树来表示其结构,用一个数组来表示,但一个二叉堆需要满足如下性质:

二叉堆的父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值

当父节点的键值大于或等于(小于或等于)它的每一个子节点的键值时,称为最大堆(最小堆)


从上图可以看出:

左图:父节点总是大于或等于其子节点,所以满足了二叉堆的性质,

右图:分支节点7作为2和12的父节点并没有满足其性质(大于或等于子节点)。

二叉堆的主要操作

insert:插入节点

delete:删除节点

max-hepify:调整分支节点堆性质

rebuildHeap:重新构建整个二叉堆

sort:排序

初始化一个二叉堆

从上面简单的介绍,我们可以知道,一个二叉堆的初始化非常的简单,它就是一个数组

初始化一个数组结构

保存数组长度

    class Heap{
        constructor(arr){
            this.data = [...arr];
            this.size = this.data.length;
        }
    }
max-heapify最大堆操作

max-heapify是把每一个不满足最大堆性质的分支节点进行调整的一个操作。

如上图:

调整分支节点2(分支节点2不满足最大堆的性质)

默认该分支节点为最大值

将2与左右分支比较,从2,12,5中找出最大值,然后和2交换位置

根据上面所将的二叉堆性质,分别得到分支节点2的左节点和右节点

比较三个节点,得到最大值的下标max

如果该节点本身就是最大值,则停止操作

将max节点与父节点进行交换

重复step2的操作,从2,4,7中找出最大值与2做交换

递归

    maxHeapify(i) {
        let max = i;
        
        if(i >= this.size){
            return;
        }
        // 当前序号的左节点
        const l = i * 2 + 1;
        // 当前需要的右节点
        const r = i * 2 + 2;
        
        // 求当前节点与其左右节点三者中的最大值
        if(l < this.size && this.data[l] > this.data[max]){
            max = l;
        }
        if(r < this.size && this.data[r] > this.data[max]){
            max = r;
        }
        
        // 最终max节点是其本身,则已经满足最大堆性质,停止操作
        if(max === i) {
            return;
        }
        
        // 父节点与最大值节点做交换
        const t = this.data[i];
        this.data[i] = this.data[max];
        this.data[max] = t;
        
        // 递归向下继续执行
        return this.maxHeapify(max);
    }
重构堆

我们可以看到,刚初始化的堆由数组表示,这个时候它可能并不满足一个最大堆或最小堆的性质,这个时候我们可能需要去将整个堆构建成我们想要的。
上面我们做了max-heapify操作,而max-heapify只是将某一个分支节点进行调整,而要将整个堆构建成最大堆,则需要将所有的分支节点都进行一次max-heapify操作,如下图,我们需要依次对12,3,2,15这4个分支节点进行max-hepify操作

具体步骤:

找到所有分支节点:上面堆的性质提到过叶子节点的序号>=Math.floor(n/2),因此小于Math.floor(n/2)序号的都是我们需要调整的节点。

例如途中所示数组为[15,2,3,12,5,2,8,4,7] => Math.floor(9/2)=4 => index小于4的分别是15,2,3,12(需要调整的节点),而5,2,8,4,7为叶子节点。

将找到的节点都进行maxHeapify操作

    rebuildHeap(){
        // 叶子节点
        const L = Math.floor(this.size / 2);
        for(let i = L - 1; i>=0; i--){
            this,maxHeapify(i);
        }
    }
最大堆排序

最大堆的排序,如上图所示:

交换首尾位置

将最后个元素从堆中拿出,相当于堆的size-1

然后在堆根节点进行一次max-heapify操作

重复以上三个步骤,知道size=0 (这个边界条件我们在max-heapify函数里已经做了)

    sort() {
        for(let i = this.size - 1; i > 0; i--){
            swap(this.data, 0, i);
            this.size--;
            this.maxHeapify(0);
        }
    }
插入和删除

这个的插入和删除就相对比较简单了,就是对一个数组进行插入和删除的操作

往末尾插入

堆长度+1

判断插入后是否还是一个最大堆

不是则进行重构堆

  insert(key) {
    this.data[this.size] = key;
    this.size++
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

删除数组中的某个元素

堆长度-1

判断是否是一个堆

不是则重构堆

  delete(index) {
    if (index >= this.size) {
      return;
    }
    this.data.splice(index, 1);
    this.size--;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }
完整代码
/**
 * 最大堆
 */

function left(i) {
  return i * 2 + 1;
}

function right(i) {
  return i * 2 + 2;
}

function swap(A, i, j) {
  const t = A[i];
  A[i] = A[j];
  A[j] = t;
}

class Heap {
  constructor(arr) {
    this.data = [...arr];
    this.size = this.data.length;
  }

  /**
   * 重构堆
   */
  rebuildHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i--) {
      this.maxHeapify(i);
    }
  }

  isHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i++) {
      const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
      const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;

      const max = Math.max(this.data[i], l, r);

      if (max !== this.data[i]) {
        return false;
      }
      return true;
    }
  }

  sort() {
    for (let i = this.size - 1; i > 0; i--) {
      swap(this.data, 0, i);
      this.size--;
      this.maxHeapify(0);
    }
  }

  insert(key) {
    this.data[this.size++] = key;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  delete(index) {
    if (index >= this.size) {
      return;
    }
    this.data.splice(index, 1);
    this.size--;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  /**
   * 堆的其他地方都满足性质
   * 唯独跟节点,重构堆性质
   * @param {*} i
   */
  maxHeapify(i) {
    let max = i;

    if (i >= this.size) {
      return;
    }

    // 求左右节点中较大的序号
    const l = left(i);
    const r = right(i);
    if (l < this.size && this.data[l] > this.data[max]) {
      max = l;
    }

    if (r < this.size && this.data[r] > this.data[max]) {
      max = r;
    }

    // 如果当前节点最大,已经是最大堆
    if (max === i) {
      return;
    }

    swap(this.data, i, max);

    // 递归向下继续执行
    return this.maxHeapify(max);
  }
}

module.exports = Heap;
总结

堆讲到这里就结束了,堆在二叉树里相对会比较简单,常常被用来做排序和优先级队列等。堆中比较核心的还是max-heapify这个操作,以及堆的三个性质。

后续

下一篇应该会介绍二叉搜索树。欢迎大家指出文章的错误,如果有什么写作建议也可以提出。我会持续的去写关于前端的一些技术文章,如果大家喜欢的话可以关注一和点个赞,你的赞是我写作的动力。
顺便再提一下,我在等第一个粉丝哈哈

以下个人公众号,欢迎大家关注,用户量达到一定的量,我会推出一些前端教学视频

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/100683.html

相关文章

  • Python数据结构——二叉堆的实现

    摘要:二叉堆的有趣之处在于,其逻辑结构上像二叉树,却是用非嵌套的列表来实现。二叉堆结构性质为了更好地实现堆,我们采用二叉树。图完全二叉树有意思的是我们用单个列表就能实现完全树。下列所示的代码是完全二叉堆的实现。 优先队列的二叉堆实现 在前面的章节里我们学习了先进先出(FIFO)的数据结构:队列(Queue)。队列有一种变体叫做优先队列(Priority Queue)。优先队列的出队(Dequ...

    stackfing 评论0 收藏0
  • 【阅读笔记】——什么是二叉

    摘要:构建二叉树构建二叉树,就是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有非叶子节点一次下沉上浮构建最大堆节点大的上浮,小的下沉构建最小堆节点小的上浮,大的下沉文章什么是二叉堆 什么是二叉堆 二叉堆的本质是一种完全二叉树,它分为两种类型:最大堆和最小堆 最大堆任何一个父节点的值,都大于等于它左右孩子的值,最小堆正好与之相反 showImg(https://segmentfault....

    big_cat 评论0 收藏0
  • 数据结构与算法学习笔记 - 优先队列、二叉堆、左式堆

    摘要:模型优先队列是允许至少下列两种操作的数据结构以及找出返回并删除优先队列中最小的元素。左式堆也是二叉树,左式堆和二叉堆的唯一区别是左式堆不是理想平衡,而实际上趋向于非常不平衡。事实上,沿左式堆的右路径是该堆中的最短路径。 6.1 模型 优先队列是允许至少下列两种操作的数据结构:insert 以及 deleteMin(找出、返回并删除优先队列中最小的元素)。 insert 操作等价于 en...

    SunZhaopeng 评论0 收藏0
  • 算法笔记-二叉

    摘要:二叉堆的概念二叉堆是一种特殊的二叉树。二叉堆分为两种最大堆和最小堆,最大堆的父节点一定大于其子节点根节点最大,最小堆的父节点小于其子节点根节点最小。这是我对二叉堆的理解,如有不对,欢迎指正,我会立即修改,谢谢。 二叉堆的概念 二叉堆是一种特殊的二叉树。二叉树是每个节点只有两个子节点的树(应该都懂吧)。二叉堆分为 两 种:最大堆和最小堆,最大堆的父节点一定大于其子...

    MrZONT 评论0 收藏0
  • JavaScript数据结构与算法(十一)二叉

    摘要:二叉堆数据结构是一种特殊的二叉树,他能高效快速的找出最大值和最小值,常应用于优先队列和著名的堆排序算法中。 二叉堆数据结构是一种特殊的二叉树,他能高效、快速的找出最大值和最小值,常应用于优先队列和著名的堆排序算法中。 二叉堆 二叉堆有以下两个特性: 是一颗完全二叉树,表示数的每一层都有左侧和右侧子节点(除最后一层的叶节点),并且最后一层的叶节点尽可能是左侧子节点 二叉堆不是最小堆就是...

    MartinHan 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<