二叉堆是一种特殊的二叉树，也叫堆数据结构,可以高效的找出最大值和最小值，常被应用于优先队列

二叉堆数据结构

二叉堆数据结构有两个特性:

  • 是一颗完全二叉树，树的每一层都有左侧和右侧节点(除了最后一层),并且最后一层叶节点都是左侧节点，称之为结构特性
  • 二叉堆不是最小堆就是最大堆。最小堆可以快速导出树的最小值，最大堆可以快速导出树的最大值，称之为堆特性

和二叉搜索树(BST)区别是：二叉搜索树左侧节点比父节点小，右侧节点比父节点大，二叉堆是每个子节点都大于等于父节点(最小堆)或者小于等于父节点(最大堆)

二叉树的数组表示

二叉树可以用链表表示，也可以用数组表示:
对于二叉树节点
image
以上就是二叉堆的数组表示

最大堆和最小堆

最小堆

1
2
3
4
5
6
7
           10
         /     \            
      15        30  
     /  \      /  \
   40    50  100   40
这是一个最小堆，任意节点比子节点小

最大堆

1
2
3
4
5
6
           15
         /     \            
      10        9  
     /  \      /  \
    7    5    3
这是一个最大堆，任意节点比子节点大

获取某个节点的左侧子节点和右侧子节点，父节点

数组形式都是通过index来操作的

  • 左侧子节点:2*index+1
  • 右侧子节点:2*index+2
  • 父节点:index/2

比如我当前的节点index是1(对应的节点key是2)，那么我的左侧子节点index就是2*1+1 = 3(也就是节点key为4)

  • 最小堆:最小值位于根节点，位于数组第一个位置
  • 最大堆:最大值位于根节点，位于数组第一个位置

    创建最小堆类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function defaultCompare (a, b) {
        if (a === b) {
          return Compare.EQUALS;
        }
        return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
      }
      // 二叉堆类
      class MinHeap {
        constructor (compareFn = defaultCompare) {
          // 比较存储在数据结构中的值用到的函数
          this.compareFn = compareFn
          this.heap = []
        }
      }

    通过index获取左侧子节点

    1
    2
    3
    4
    // 通过index获取左侧子节点
    getLeftIndex(index) {
      return 2*index + 1
    }

    通过index获取右侧子节点

    1
    2
    3
    4
    // 通过index获取左侧子节点
    getRightIndex(index) {
      return 2*index + 2
    }

    通过index获取父节点

    1
    2
    3
    4
    5
    6
    getParentIndex(index) {
         if (index === 0) {
           return undefined
         }
         return Math.floor((index-1)/2)
       }

    向堆中插入值

    向堆中插入一个值，如果插入成功，就会返回true，否则返回false
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // 当前插入节点的index
        siftUp (index) {
          // 获取到父节点的index
          let parentIndex = this.getParentIndex(index)
          // index > 0
          // 比较父节点和当前节点大小的值，如果当前节点比父节点小，由这个节点和父节点进行实际的节点交换
          while (index > 0 && this.compareFn(this.heap[parentIndex],this.heap[index]) === Compare.BIGGER_THAN) {
            // 二叉堆数组, 父节点index，当前插入节点的index
            swap(this.heap,parentIndex,index)
            // 交换之后，index就是原来的parentIndex
            index = parentIndex
            // 在获取原来的parentIndex的父index
            parentIndex = this.getParentIndex(index)
          }
        }
        
    const swap = (array, a, b) => [array[a],array[b]] = [array[b],array[a]]

    // 测试插入值
      const heap = new MinHeap()
      heap.insert(2)
      heap.insert(3)
      heap.insert(4)
      heap.insert(5)
      heap.insert(1)
      console.log(heap) // [1,2,4,5,3]
    image

    从堆中找到最大值或者最小值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 获取堆长度
    size() {
      return this.heap.length
    }
    isEmpty () {
      return this.size() === 0
    }
    findMin() {
      return this.isEmpty() ? undefined : this.heap[0]
    }

    移除最小堆中的值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    // 移除堆中的最小值或者最大值
        // 直接移除掉第一个元素，然后将末尾的元素赋值到第一个，在不断进行遍历替换
        extract() {
          if (this.isEmpty()) {
            return undefined
          }
          if (this.size() === 1) {
            return this.heap.shift()
          }
          const removedValue = this.heap.shift()
          // 和siftUp操作相反
          this.siftDown(0)
          return removedValue
        }
        // 向下移动
        siftDown(index) {
          // index为0
          let element = index
          // index为根节点 获取左侧第一个子节点索引
          const left = this.getLeftIndex(index)
          // index为根节点 获取右侧第一个子节点索引
          const right = this.getRightIndex(index)
          // 获取当前节点的长度length
          const size = this.size()
          if (left < size && this.compareFn(this.head[element], this.heap[left] > Compare.BIGGER_THAN)) {
            element = left
          }
          if (right < size && this.compareFn(this.head[element], this.heap[right] > Compare.BIGGER_THAN)) {
            element = right
          }
          if (element !== index) {
            swap(this.heap, index, element)
            this.siftDown(element)
          }
        }

    最大堆

    和最小堆代码相同，但是需要修改一下比较大小的大于换成小于
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 最大堆
    class MaxHeap extends MinHeap {
      constructor(compareFn = defaultCompare) {
        super(compareFn)
        this.compareFn = reverseCompare(compareFn)
      }
    }
    // 利用函数柯里化
    function reverseCompare(compareFn) {
      return (a, b) => compareFn(b, a)
    }