堆

原文链接：https://note.noxussj.top/?source=sifo

什么是堆？

堆是一种非凡的齐全二叉树。齐全二叉树的含意就是每层节点都齐全填满，除了最初一层外只容许最左边短少若干个节点。在 JavaScript 中通常用数组示意堆（依照广度优先遍历程序）。

最大堆

最小堆

个性

  • 所有的节点都大于等于它的子节点（最大堆）
  • 或者所有的节点都小于等于它的子节点（最小堆）
  • 左侧子节点的地位是 2 _ index + 1
  • 右侧子节点的地位是 2 _ index + 2 （也就是在左子节点的根底上 + 1）
  • 父节点的地位是 (index - 1) / 2

长处

  • 高效、疾速的找出堆的最大值和最小值，工夫复杂度是 O (1)
  • 找出第 K 个最大、最小元素

罕用操作

插入
  • 将值插入堆的底部，即数据的尾部
  • 而后上移，将这个值和它父节点进行替换，直到父节点小于等于这个插入的值

  • 大小为 k 的堆中插入元素的工夫复杂度为 O (logK)

    删除堆顶
  • 用数组尾部元素替换堆顶（间接删除堆顶会毁坏构造）
  • 而后下移，将新堆顶和它的子节点进行替换，直到子节点大于等于这个新堆顶

  • 大小为 k 的堆中删除堆顶的工夫复杂度为 O (logK)

    获取堆顶

  • 返回数组的第 0 项

    获取堆大小
  • 返回数组的长度

根底案例

通过 Class 实现最小堆

    class MinHeap {        constructor() {            this.heap = []        }            top() {            return this.heap[0]        }            size() {            return this.heap.length        }            getChildLeftIndex(i) {            return i * 2 + 1        }            getChildRightIndex(i) {            return i * 2 + 2        }            getParentIndex(i) {            return (i - 1) >> 1        }            swap(index1, index2) {            const temp = this.heap[index1]            this.heap[index1] = this.heap[index2]            this.heap[index2] = temp        }            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)            }        }            shiftDown(index) {            const leftChildIndex = this.getChildLeftIndex(index)            const rightChildIndex = this.getChildRightIndex(index)                if (this.heap[leftChildIndex] < this.heap[index]) {                this.swap(leftChildIndex, index)                this.shiftDown(leftChildIndex)            }                if (this.heap[rightChildIndex] < this.heap[index]) {                this.swap(rightChildIndex, index)                this.shiftDown(rightChildIndex)            }        }            insert(value) {            this.heap.push(value)            this.shiftUp(this.heap.length - 1)        }            pop() {            this.heap[0] = this.heap.pop()            this.shiftDown(0)        }    }        const h = new MinHeap()    h.insert(3)    h.insert(2)    h.insert(1)    h.pop()

原文链接：https://note.noxussj.top/?source=sifo