JavaScript 数据结构与算法 之 二叉堆和堆排序

二叉堆和堆排序

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

数据结构

特性

• 结构特性：它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点

• 堆特性：二叉堆不是最小堆就是最大堆

  • 最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值
  • 所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点

function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}
class MinHeap {
  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);
  }
  insert(value) {
    if (value != null) {
      this.heap.push(value);
      this.siftUp(this.heap.length - 1);
      return true;
    }
    return false;
  }
  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 = parent;
      parent = this.getParentIndex(index);
    }
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.size() === 0;
  }
  findMinimum() {
    return this.isEmpty() ? undefined : this.heap[0];
  }
  extract() {
    if (this.isEmpty()) {
      return undefined;
    }
    if (this.size() === 1) {
      return this.heap.shift();
    }
    const removedValue = this.heap.shift();
    this.sifDown(0);
    return removedValue;
  }
  sifDown(index) {
    let element = index;
    const left = this.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();
    if (left < size &&
      this.compareFn(this.heap[element], this.heap[left]) > Compare.BIGGER_THAN) {
        element = left;
    }
    if (right < size &&
      this.compareFn(this.heap[element], this.heap[right]) > Compare.BIGGER_THAN) {
        element = right;
    }
    if (index !== element) {
      swap(this.heap, index, element);
      this.sifDown(element);
    }
  }
}
function reverseCompare(compareFn) {
  return (a, b) => compareFn(b, a);
}
class MaxHeap extends MinHeap {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = reverseCompare(compareFn);
  }
}

堆排序

思路

1. 用数组创建一个最大堆用作源数据
2. 在创建最大堆后，最大的值会被存储在堆的第一个位置，我们要将它替换为堆的最后一个值，将堆的大小减 1
3. 最后，我们将堆的根节点下移并重复步骤 2 直到堆的大小为 1

function heapSort(array, compareFn = defaultCompare) {
  let heapSize = array.length;
  buildMaxHeap(array, compareFn);
  while (heapSize > 1) {
    swap(array, 0, --heapSize);
    heapify(array, 0, heapSize, compareFn);
  }
  return array;
}
function buildMaxHeap(array, compareFn) {
  for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
    heapify(array, i, array.length, compareFn);
  }
  return array;
}