侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

Heap(堆)

前端  /  管理员 发布于 8年前   537
目录
一、是什么
二、操作
插入
删除
时间复杂度
三、总结
参考文献

Heap

# 面试官:说说你对堆的理解?如何实现?应用场景?

# 一、是什么

堆(Heap)是计算机科学中一类特殊的数据结构的统称

堆通常是一个可以被看做一棵完全二叉树的数组对象,如下图:

总是满足下列性质:

  • 堆中某个结点的值总是不大于或不小于其父结点的值
  • 堆总是一棵完全二叉树

堆又可以分成最大堆和最小堆:

  • 最大堆:每个根结点,都有根结点的值大于两个孩子结点的值
  • 最小堆:每个根结点,都有根结点的值小于孩子结点的值

# 二、操作

堆的元素存储方式,按照完全二叉树的顺序存储方式存储在一个一维数组中,如下图:

用一维数组存储则如下:

[0, 1, 2, 3, 4, 5, 6, 7, 8]
1

根据完全二叉树的特性,可以得到如下特性:

  • 数组零坐标代码的是堆顶元素
  • 一个节点的父亲节点的坐标等于其坐标除以2整数部分
  • 一个节点的左节点等于其本身节点坐标 * 2 + 1
  • 一个节点的右节点等于其本身节点坐标 * 2 + 2

根据上述堆的特性,下面构建最小堆的构造函数和对应的属性方法:

class MinHeap {
  constructor() {
    // 存储堆元素
    this.heap = []
  }
  // 获取父元素坐标
  getParentIndex(i) {
    return (i - 1) >> 1
  }

  // 获取左节点元素坐标
  getLeftIndex(i) {
    return i * 2 + 1
  }

 // 获取右节点元素坐标
  getRightIndex(i) {
    return i * 2 + 2
  }

  // 交换元素
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }

  // 查看堆顶元素
  peek() {
    return this.heap[0]
  }

  // 获取堆元素的大小
  size() {
    return this.heap.length
  }
}

涉及到堆的操作有:

  • 插入
  • 删除

# 插入

将值插入堆的底部,即数组的尾部,当插入一个新的元素之后,堆的结构就会被破坏,因此需要堆中一个元素做上移操作

将这个值和它父节点进行交换,直到父节点小于等于这个插入的值,大小为k的堆中插入元素的时间复杂度为O(logk)

如下图所示,22节点是新插入的元素,然后进行上移操作:

相关代码如下:

// 插入元素
insert(value) {
  this.heap.push(value)
  this.shifUp(this.heap.length - 1)
}

// 上移操作
shiftUp(index) {
  if (index === 0) { return }
  const parentIndex = this.getParentIndex(index)
  if(this.heap[parentIndex] > this.heap[index]){
    this.swap(parentIndex, index)
    this.shiftUp(parentIndex)
  }
}

# 删除

常见操作是用数组尾部元素替换堆顶,这里不直接删除堆顶,因为所有的元素会向前移动一位,会破坏了堆的结构

然后进行下移操作,将新的堆顶和它的子节点进行交换,直到子节点大于等于这个新的堆顶,删除堆顶的时间复杂度为O(logk)

整体如下图操作:

相关代码如下:

// 删除元素
pop() {
  this.heap[0] = this.heap.pop()
  this.shiftDown(0)
}

// 下移操作
shiftDown(index) {
  const leftIndex = this.getLeftIndex(index)
  const rightIndex = this.getRightIndex(index)
  if (this.heap[leftIndex] < this.heap[index]){
    this.swap(leftIndex, index)
    this.shiftDown(leftIndex)
  }
  if (this.heap[rightIndex] < this.heap[index]){
    this.swap(rightIndex, index)
    this.shiftDown(rightIndex)
  }
}

# 时间复杂度

关于堆的插入和删除时间复杂度都是Olog(n),原因在于包含n个节点的完全二叉树,树的高度不会超过log2n

堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是Olog(n),插入数据和删除堆顶元素的主要逻辑就是堆化

# 三、总结

  • 堆是一个完全二叉树
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值
  • 对于每个节点的值都大于等于子树中每个节点值的堆,叫作“大顶堆”
  • 对于每个节点的值都小于等于子树中每个节点值的堆,叫作“小顶堆”
  • 根据堆的特性,我们可以使用堆来进行排序操作,也可以使用其来求第几大或者第几小的值

# 参考文献

  • https://baike.baidu.com/item/%E5%A0%86/20606834
  • https://xlbpowder.cn/2021/02/26/%E5%A0%86%E5%92%8C%E5%A0%86%E6%8E%92%E5%BA%8F/

  • 上一条:
    BinarySearch(前端实现二分查找算法,也称折半搜索算法)
    下一条:
    Laravel 5框架学习之Laravel入门和新建项目
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 使用 Alpine.js 排序插件对元素进行排序(0个评论)
    • 在js中使用jszip + file-saver实现批量下载OSS文件功能示例(0个评论)
    • 在vue中实现父页面按钮显示子组件中的el-dialog效果(0个评论)
    • 使用mock-server实现模拟接口对接流程步骤(0个评论)
    • vue项目打包程序实现把项目打包成一个exe可执行程序(0个评论)
    • 近期文章
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • 在go + gin中gorm实现指定搜索/区间搜索分页列表功能接口实例(0个评论)
    • 在go语言中实现IP/CIDR的ip和netmask互转及IP段形式互转及ip是否存在IP/CIDR(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • Laravel 11.15版本发布 - Eloquent Builder中添加的泛型(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-10
    • 2017-11
    • 2018-03
    • 2018-04
    • 2018-05
    • 2018-06
    • 2018-09
    • 2018-11
    • 2018-12
    • 2019-02
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2021-04
    • 2021-05
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客