二叉堆 - wangshengliang

基本概念

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

二叉堆分为两种：

最小堆：特点是每个子节点都大于等于父节点，因此在最小堆中可以快速找出最小值
最大堆：每个子节点都小于等于父节点，因此在最大堆中可以快速找出最大值

二叉堆本质上也是一颗完全二叉树，但是和前面介绍过的二叉搜索树又有一定的区别：

二叉搜索树：左侧子节点总是比父节点小，右侧子节点总是比父节点大

;[4, 2, 7, 1, 3, 6, 5]

二叉堆的存储

仍然使用数组来存储二叉堆。

已知一个节点的索引下标值 index，可以求出：

左子节点的下标值： 2 * index + 1
右子节点的下标值: 2 * index + 2
父节点的下标值：Math.floor((index - 1) / 2)

实现代码

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0,
}
function defaultCompare(a, b) {
  if (a === b) return Compare.EQUALS
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}

function swap(array, a, b) {
  ;[array[a], array[b]] = [array[b], array[a]]
}

module.exports = {
  defaultCompare,
  swap,
  Compare,
}

const { defaultCompare, swap, Compare } = require('./utils.js')
// 最小堆类
class MinHeap {
  /**
   * compareFn - 比较方法
   */
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn
    this.heap = [] // 用于存储最小堆所有元素
  }
  // 获取左子节点下标
  getLeftIndex(index) {
    return 2 * index + 1
  }
  // 获取右子节点下标
  getRightIndex(index) {
    return 2 * index + 2
  }
  // 获取父节点
  getParentIndex(index) {
    if (index === 0) return undefined
    return Math.floor((index - 1) / 2)
  }
  // 获取当前最小堆的最小值
  // 最小堆中，堆顶的元素就是最小的，是数组的第一个元素
  findMini() {
    return this.isEmpty() ? undefined : this.heap[0]
  }
  // 还有一些工具方法
  size() {
    return this.heap.length
  }
  isEmpty() {
    return this.size() <= 0
  }
  clear() {
    this.heap = []
  }
  getAsArray() {
    // 就是获取内部存储了元素的数组
    return this.heap
  }
}

新增元素

当向一个最小堆新增一个元素的时候，需要对该元素做 上移操作，如下图所示：

insert(value){
  if(value !== null){
    // 执行插入操作

    // 获取新元素应该插入的位置
    const index = this.heap.length;
    this.heap.push(value);
    // 接下来就需要向上调整
    this.siftUp(index); // 传入新元素的下标
    return true;
  }
  return false;
}

/**
 * index - 一开始元素的下标
 */
siftUp(index){
  // 先获取父节点的下标
  let parent = this.getParentIndex(index);

  // 接下来循环和父节点做比较以及交换操作
  while(index > 0 &&
        this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
     ){
    // 两个节点需要进行交换
    swap(this.heap, parent, index);
    // 更新 index 的值，后面方便根据新的 index 寻找下一个父节点
    index = parent;
    // 继续寻找父节点的下标
    parent = this.getParentIndex(index);
  }
}

提取元素

一般来讲，形成一个最大或最小堆，主要目的就是为了获取当前的最值。在二叉堆中要获取最值的方法很简单，直接移除数组中的第一个元素即可。但是呢，又没有那么简单，因为移除了第一个元素，我们就得重新构造新的二叉堆，将新的最值放置于最上面。

🙋那么这里就涉及到一个问题，如何确定新的最值，放置到最上面呢？

回答：一般来讲，是将最后一个元素放到头部

然后重新进行 下移操作，如下图所示：

在最小堆的 siftDown 过程中，通常需要同时比较左右子结点并选择其中更小的那个进行下一步的交换和下滤。也就是说，如果只和左子结点进行比较，可能忽略了右子结点比左子结点更小的情况，导致堆序破坏。

// 从堆顶提取最值
extract(){
  if(this.isEmpty()) return undefined;
  // 如果整个二叉堆只有一个元素，直接弹出，不需要做下移处理
  if(this.size() === 1) return this.heap.shift();

  // 下面说明不止一个元素，那么需要做下移处理
  const removedValue = this.heap[0]; // 先存储最值
  this.heap[0] = this.heap.pop(); // 将最后一个元素弹出，作为新的堆顶元素
  this.siftDown(0);

  // 向外界返回之前缓存的最值
  return removedValue;
}

siftDown(index){
  let element = index;
  // 先获取左右子节点的下标
  const left = this.getLeftIndex(index); // 左子节点下标
  const right = this.getRightIndex(index); // 右子节点下标
  const size = this.size();

  // 先比较左边的子节点，当前 element 对应的节点是父节点
  if(left < size &&
     this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN
  ){
    // 需要记录新的左子节点下标
    element = left;
  }

  // 然后再比较右子节点，当前 element 对应的节点可能是父节点，也可能是左子节点
  if(right < size &&
     this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN
  ){
    // 需要记录新的右子节点下标
    element = right;
  }

  // 如果发现比父节点更小的子节点，那么就需要交换并且递归向下继续调整
  if(element !== index){
    swap(this.heap, index, element);
    this.siftDown(element); // 继续往下调整
  }
}

堆化处理

所谓堆化，指的就是将 无序的数组 调整成一个满足最小堆（或者最大堆）的堆结构。

在进行调整的时候，叶子节点是不需要调整的，因为它们没有子节点。因此我们在调整的时候，需要先找到非叶子节点。

寻找非叶子节点范围：从 0 到 Math.floor(size / 2) - 1

非叶子节点：从 0 到 Math.floor(5 / 2) - 1 = 从 0 到 1

/**
 * array - 无序的数组
 */
heapify(array){
  if(array){
    // 如果传入了数组，先复制一份给当前堆，避免修改原来的数组
    this.heap = [...array];
  }

  // 接下来就需要找非叶子节点最大的索引值
  const maxIndex = Math.floor(this.size() / 2) - 1;
  // 接下来就需要对每一个非叶子节点进行向下调整
  // 这里从最后一个非叶子节点一直调整到根节点
  for(let i = maxIndex; i >= 0; i--){
    this.siftDown(i);
  }

  return this.heap;

}

最大堆

function reverseCompare(compareFn) {
  return (a, b) => compareFn(b, a)
}

class MaxHeap extends MinHeap {
  constructor(compareFn = defaultCompare) {
    super(compareFn)
    this.compareFn = reverseCompare(compareFn)
  }
}

React中的最小堆

在 React 中，实际上就利用了最小堆来管理 Scheduler 内部的优先级队列。

// 两个任务队列
var taskQueue: Array<Task> = []
var timerQueue: Array<Task> = []

push(timerQueue, newTask) // 像数组中推入一个任务
pop(timerQueue) // 从数组中弹出一个任务
timer = peek(timerQueue) // 从数组中获取第一个任务

最小堆对应的源码在 SchedulerMinHeap.js 文件中，总共有 6 个方法，其中向外暴露了 3 个方法

push：向最小堆推入一个元素。因为使用的是数组，所以在推入任务的时候，首先该任务是被推入到数组的最后一项，但是这个时候，涉及到一个调整，我们需要向上调整，把这个任务调整到合适的位置。
```
push(timerQueue, newTask)
export function push(heap, node) {
  const index = heap.length
  // 推入到数组的最后一位
  heap.push(node)
  // 向上调整，调整到合适的位置
  siftUp(heap, node, index)
}
```

pop：从任务堆里面弹出第一个任务，也就是意味着该任务已经没有在队列里面了。

pop(taskQueue)
export function pop(heap) {
  if (heap.length === 0) {
    return null
  }
  // 获取数组的第一个任务（一定是最小的）
  const first = heap[0]
  // 拿到数组的最后一个
  const last = heap.pop()
  if (last !== first) {
    // 将最后一个任务放到第一个
    heap[0] = last
    // 接下来向下调整
    siftDown(heap, last, 0)
  }
  return first
}

peek：取出堆顶的任务，堆顶一定是最小的。这个方法极其的简单

peek(timerQueue)
export function peek(heap) {
  // 返回这个数组的第一个元素
  return heap.length === 0 ? null : heap[0]
}

没有暴露的是：

siftUp：向上调整
siftDown：向下调整
compare：这是一个辅助方法，就是两个元素做比较的

这 3 个方法可以参阅 React 中 Scheduler 相关源码。

-EOF-