重温数据结构最大堆

在 JavaScript 中没有最大堆以及最小堆这样的 API 供大家直接使用。因此涉及到堆这样的一些数据结构，前端同学可能往往无从下手。下面整理了关于最大堆、最小堆、堆排序、最小优先队列的一些知识，供大家参考。

几个概念

以下几个概念囊括了关于堆这种数据结构中所有需要的基础知识

1、完全二叉树

如果二叉树除了最后一层有缺失外，其它是满的，且最后一层缺失的叶子结点只出现在右侧，则这样的二叉树叫完全二叉树。定义是：若二叉树的深度为 n，除第 n 层外，其余各层的结点都达到了最大，且第 n 层的结点都连续集中在最左边。简而言之，就是从左到右结点是连续不断的二叉树就叫完全二叉树。满二叉树是特殊的完全二叉树。

2、顺序存储

完全二叉树可以采用数组这种基础数据结构来存储，因为其其节点是完全连续的，且具有以下特点：

以 i 为下标（注意从 0 开始计算）的节点，其节点关系具有以下规律

父节点： Math.floor(i / 2) - 1

左子节点：2*i + 1

右子节点：2*i + 2

3、最大堆

二叉树的任何一节点的值都大于其左、右子节点的值，其中根节点的值最大

4、最小堆

二叉树的任何一节点的值都小于其左、右子节点的值，其中根节点的值最小

5、堆排序

基于最大堆的一种选择排序方法，不稳定，时间复杂度 O(nlogN)

6、最大优先队列、最小优先队列

基于最大堆和最小堆的一种高级数据结构，可以完成以下操

• 将元素插入集合、INSERT
• 返回最大（小）元素、MAXIMUM
• 去掉最大（小）元素、EXTRACT-MAX
• 将某元素的值增加 INCRESE-KEY

建堆

创建堆的过程主要包括以下两个步骤，以最大堆为例，最小堆同理：

• 堆化 maxHeapify
• 交换 swap
• 从非叶子节点依次堆化 buildMaxHeap

// 完成数组元素交换
Heap.prototype.swap = function (nums, i, j) {
  [nums[i], nums[j]] = [nums[j], nums[i]];
};

// 从非叶子节点开始堆化
Heap.prototype.buildMaxHeap = function () {
  for (let i = Math.floor(this.size / 2) - 1; i >= 0; i--) {
    this.maxHeapify(i);
  }
};

// 一个节点的堆化过程
Heap.prototype.maxHeapify = function (i) {
  let l = i * 2 + 1;
  let r = i * 2 + 2;
  let largest = i;
  if (l < this.size && this.nums[l] > this.nums[largest]) {
    largest = l;
  }
  if (r < this.size && this.nums[r] > this.nums[largest]) {
    largest = r;
  }

  if (largest !== i) {
    this.swap(this.nums, i, largest);
    this.maxHeapify(largest);
  }
};

堆排序

堆排序的过程是将根节点移除，然后将剩余节点调整成最大堆的过程，循环至结束，堆排序的最坏时间复杂度为 O(nlogN)

/**
 * 选择排序的思路（背后基于最大堆这种结构）
 * 排序结束后，根节点即为第K大数
 * @param {number} k 第几顺位
 */
Heap.prototype.sortByMaxHeap = function (k) {
  for (let i = this.nums.length - 1; i >= this.nums.length - k + 1; i--) {
    this.swap(this.nums, 0, i);
    this.size--;
    this.maxHeapify(0);
  }
};