面试官：说说你对堆的理解？如何实现？应用场景？

r囧r小猫 2022-09-13 13:30 219阅读 0赞

![27a36bab3c5160343feb9f8dfb5d7920.png][]

## 一、是什么 ##

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

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

![873f39a127e368129b7cc6153d511918.png][]

总是满足下列性质：

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

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

*  最大堆：每个根结点，都有根结点的值大于两个孩子结点的值
 *  最小堆：每个根结点，都有根结点的值小于孩子结点的值

## 二、操作 ##

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

![5fa98fd2bb9089c826f2d4162f1516d3.png][]

用一维数组存储则如下：

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

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

*  数组零坐标代码的是堆顶元素
 *  一个节点的父亲节点的坐标等于其坐标除以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节点是新插入的元素，然后进行上移操作：

![2d7170a243919e8ab4bb21ae4d0d4b92.png][]

相关代码如下：

// 删除元素
    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/

\--The End--

系列正在更新：8/18

点击下方卡片解锁更多

![25998066212d251dbf0c01fcb4aa17ad.png][]

创作不易，星标、点赞、在看 三连支持

[27a36bab3c5160343feb9f8dfb5d7920.png]: /images/20220828/ef98a81bc8b04a54a26e20070bc6fc3f.png
[873f39a127e368129b7cc6153d511918.png]: /images/20220828/5140d4fc292348ff83acddeefb98adc9.png
[5fa98fd2bb9089c826f2d4162f1516d3.png]: /images/20220828/234e3555988d4cd9b01209b9b52949c4.png
[2d7170a243919e8ab4bb21ae4d0d4b92.png]: /images/20220828/ecf9267544b34cb49c1d7695cffe60cf.png
[15e6c31e46d9a7e85159ffb766a784cf.png]: /images/20220828/26fc5427a72c4a5cab25cab69e905869.png
[25998066212d251dbf0c01fcb4aa17ad.png]: /images/20220828/8b03a00ead454c22aebecd02cb89bbf6.png