数据结构与算法-二叉堆

# 数据结构与算法-二叉堆

二叉堆是一种特殊的二叉树，也就是堆数据结构。二叉堆是计算机科学中一种非常著名的数据结构，由于它能高效、快速地找出最大值和最小值，常被应用于优先队列。它也被用于著名的堆排序算法中。

# 二叉堆简介

二叉堆是一种特殊的二叉树，有以下两个特性：

结构特性：它是一棵完全二叉树
- 除了二叉树最后一层外，其他各层的节点数都达到了最大值；
- 并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；
- 完美二叉树是特殊的完全二叉树；
堆特性：二叉堆不是最小堆就是最大堆。
- 最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值。
- 所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。

下图展示了一些合法的和不合法的堆

尽管二叉堆是二叉树，但并不一定是二叉搜索树（BST）。在二叉堆中，每个子节点都要大于等于父节点（最小堆）或小于等于父节点（最大堆）。然而在二叉搜索树中，左侧子节点总是比父节点小，右侧子节点也总是更大。

我们这里具体来分析最小堆，最大堆同理，不再赘述。

# 最小堆

创建一个堆类

class MinHeap {
  constructor () {
    this.heap = []
  }
}

# 节点关系

我们前面也分析过，二叉树的表示方式有两种：

第一种使用一个动态的表示方式，也就是指针（用节点表示），即使用链表
第二种是使用一个数组，通过索引值检索父节点、左子和右子节点的值

要访问使用普通数组的二叉树节点，我们可以用下面的方式操作index。

对于给定位置index的节点：

它的左子节点的位置是index * 2 + 1（如果位置可用）；
它的右侧子节点的位置是 index * 2 + 2（如果位置可用）；
它的父节点位置是 (index - 1) / 2，向下取整（如果位置可用）。

那么，查找父、子节点的方法可定义：

// 父节点索引
getParentIndex (index) {
  if (index === 0) {
    return undefined
  }

  return Math.floor(((index - 1) / 2))
}

// 左子节点索引
getLeftIndex (index) {
  return index * 2 + 1
}

// 右子节点索引
getRightIndex (index) {
  return index * 2 + 2
}

# 常见操作

可以在堆数据结构中进行三个主要操作。

insert(value)：向堆中插入一个新的值。如果插入成功，它返回true，否则返回false。

extract()：移除最小值（最小堆）或最大值（最大堆），并返回这个值。

findMinimum()：返回最小值（最小堆）或最大值（最大堆）且不会移除这个值。

# 插入

向堆中插入值是指将值插入堆的底部叶节点（数组的最后一个位置）再执行heapifyUp方法，表示我们将要将这个值和它的父节点进行交换，直到父节点小于这个插入的值。这个上移操作也被称为up head、percolate up、bubble up、heapify up或cascade up。

/**
 * 向堆中插入一个新的值
 * @param {*} key 
 */
insert (val) {
  if (typeof val === 'number') {
    // 将值插入堆的底部叶节点
    this.heap.push(val)
    // 将这个值上移直至父节点小于这个插入的值
    this.heapifyUp(this.heap.length - 1)
    return true
  }
  return false
}
// 上移 接收插入值的位置作为参数
heapifyUp (index) {
  // 获取其父节点的位置
  let parentIndex = this.getParentIndex(index)

  while (index > 0 && this.heap[index] < this.heap[parentIndex]) {
    // 插入的值小于它的父节点，将这个值和父节点值交换，一直比较到根节点
    this.swap(index, parentIndex)
    index = parentIndex
    parentIndex = this.getParentIndex(index)
  }
}

insert方法的实际操作，有如下结构：

假设我们想要向堆中插入一个值1。算法会进行一些少量的上移操作，如下图所示

# 删除堆中最小值

移除最小值（最小堆）或最大值（最大堆）表示移除数组中的第一个元素（堆的根节点）。在移除后，我们将堆的最后一个元素移动至根部并执行heapifyDown函数，表示我们将交换元素直到堆的结构正常。这个下移操作也被称为sink down、percolate down、bubble down、heapify down或cascade down。

/**
 * 移除最小值，并返回这个值
 */
extract () {
  if (this.isEmpty()) {
    return undefined
  }

  if (this.size() === 1) {
    return this.heap.shift()
  }

  // 堆中有不止一个值，移除第一个值并将堆中最后一个元素移动至根部
  const min = this.heap[0]
  this.heap[0] = this.heap.pop()
  // 下移新的根元素直至堆结构正常
  this.heapifyDown(0)

  return min
}
// 下移(堆化)，接收下移元素的位置作为参数
heapifyDown (index) {
  const leftIndex = this.getLeftIndex(index)
  const rightIndex = this.getRightIndex(index)

  let minIndex = index // 记录两个值比较时的最小索引 默认是本身

  if (index < this.size() && this.heap[minIndex] > this.heap[leftIndex]) {
    // 左子节点更小 记录更小的左子节点索引
    minIndex = leftIndex
  }

  if (index < this.size() && this.heap[minIndex] > this.heap[rightIndex]) {
    // 再比对 右子节点更小 记录更小的左子节点索引
    minIndex = rightIndex
  }

  if (index !== minIndex) {
    // 索引不同，说明minIndex位置的元素更小，交换位置 即 下移index索引的元素
    this.swap(index, minIndex)
    // 递归 对比交换后minIndex位置的值与其左右子节点的值，是否是最小的，不是最小的继续下移
    this.heapifyDown(minIndex)
  }
}

假设我们从堆中进行导出操作。算法会进行一些下移操作，如下图所示。

# 完整实现

/**
 * 小顶堆
 */
module.exports = class MinHeap {
  constructor () {
    this.heap = []
  }

  getHeap () {
    return this.heap
  }

  size () {
    return this.heap.length
  }

  isEmpty () {
    return this.size === 0
  }

  clear () {
    this.heap = []
  }

  // 父节点索引
  getParentIndex (index) {
    if (index === 0) {
      return undefined
    }

    return Math.floor(((index - 1) / 2))
  }

  // 左子节点索引
  getLeftIndex (index) {
    return index * 2 + 1
  }

  // 右子节点索引
  getRightIndex (index) {
    return index * 2 + 2
  }

  // 交换两索引位置的值
  swap (indexA, indexB) {
    [this.heap[indexA], this.heap[indexB]] = [this.heap[indexB], this.heap[indexA]]
  }

  // 返回堆中最小值，且不会移除这个值
  min () {
    return this.isEmpty() ? undefined : this.heap[0]
  }

  /**
   * 向堆中插入一个新的值
   * @param {*} key 
   */
  insert (val) {
    if (typeof val === 'number') {
      // 将值插入堆的底部叶节点
      this.heap.push(val)
      // 将这个值上移直至父节点小于这个插入的值
      this.heapifyUp(this.heap.length - 1)
      return true
    }
    return false
  }
  // 上移 接收插入值的位置作为参数
  heapifyUp (index) {
    // 获取其父节点的位置
    let parentIndex = this.getParentIndex(index)

    while (index > 0 && this.heap[index] < this.heap[parentIndex]) {
      // 插入的值小于它的父节点，将这个值和父节点值交换，一直比较到根节点
      this.swap(index, parentIndex)
      index = parentIndex
      parentIndex = this.getParentIndex(index)
    }
  }

  /**
   * 移除最小值，并返回这个值
   */
  extract () {
    if (this.isEmpty()) {
      return undefined
    }

    if (this.size() === 1) {
      return this.heap.shift()
    }

    // 堆中有不止一个值，移除第一个值并将堆中最后一个元素移动至根部
    const min = this.heap[0]
    this.heap[0] = this.heap.pop()
    // 下移新的根元素直至堆结构正常
    this.heapifyDown(0)

    return min
  }
  // 下移(堆化)，接收下移元素的位置作为参数
  heapifyDown (index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)

    let minIndex = index // 记录两个值比较时的最小索引 默认是本身

    if (index < this.size() && this.heap[minIndex] > this.heap[leftIndex]) {
      // 左子节点更小 记录更小的左子节点索引
      minIndex = leftIndex
    }

    if (index < this.size() && this.heap[minIndex] > this.heap[rightIndex]) {
      // 再比对 右子节点更小 记录更小的左子节点索引
      minIndex = rightIndex
    }

    if (index !== minIndex) {
      // 索引不同，说明minIndex位置的元素更小，交换位置 即 下移index索引的元素
      this.swap(index, minIndex)
      // 递归 对比交换后minIndex位置的值与其左右子节点的值，是否是最小的，不是最小的继续下移
      this.heapifyDown(minIndex)
    }
  }
}

测试

const minHeap = new MinHeap()

minHeap.insert(9)
minHeap.insert(8)
minHeap.insert(7)
minHeap.insert(6)
minHeap.insert(5)
minHeap.insert(4)
minHeap.insert(3)
minHeap.insert(2)
minHeap.insert(1)

// getHeap
console.log(minHeap.getHeap())

// extract
console.log(minHeap.extract())

// getHeap
console.log(minHeap.getHeap())

// min
console.log(minHeap.min())

编辑

上次更新: 2022/01/24, 18:40:59

← 数据结构与算法-红黑树（二）数据结构与算法-图→