堆的定义

堆（heap），是一种数据结构

根据 维基百科 的定义，堆 是一种特别的二叉树，满足以下条件的二叉树，可以称之为 堆：

• 完全二叉树；
• 每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。

堆的优势：

• 插入和删除都是O(lg n)
• 取最大/最小值得时间为O(1)

根据父子节点值的关系，堆可以分为：

• 最大堆(max-heap)，子节点的值小于等于父节点
• 最小堆(min-heap)，子节点的值大于等于父节点

最大堆的实现

在JS里，没有内置的堆，也没有优先队列，所以得自己手动实现。
一般堆是由数组来实现的，堆是一颗完全二叉树，其每个节点从上到下，从左到右排好序后。

这里有几个点要重点说明一下：

1. 堆的起始序号是1而不是0
2. 节点x的左子节点为2x，右子节点为2x+1，父节点为x/2
3. 堆的长度为n, 则[n/2 + 1…n]都是叶子节点
4. 我们在用堆的序号访问数组时需要-1

maxHeapify

对于树的算法，一般递归是简单且直观的。
我们先定义一个操作，它可以将一个子树最大堆化。

// h 为堆数组
// i 为子树的根节点下标
// size 为堆的大小
function maxHeapify(h, i, size) {}

我们假设该子树的左右节点都是最大堆。
首先我们判断根节点，左右子节点的值大小，如果子节点的值大于根节点，则互换。
最后对被换掉的节点进行再最大堆化(递归)。

tip: 注意数组的长度可能比实际的堆大，所以我们需要一个size表示堆的大小。

buildMaxHeap

有了对子树进行堆化的操作，我们就可以循环递归将整个数组堆化。
由于我们的假设是子树都是最大堆，那么我们应该是从子节点开始往上堆化。也就是说我们得从数组的尾部往前进行迭代。因为堆的尾部都是子节点，而子节点满足最大堆的特性。

function buildMaxHeap(nums) {
  for (let i = nums.length; i > 0; i--) {
    maxHeapify(nums, i, nums.length);
  }

  return nums;
}

最小堆

实现完最大堆后其实最小堆也就是判断条件变了而已。

算法题：堆排序

原理：堆的堆顶元素一定是最大/小值，我们每次将堆顶元素和堆尾元素互换，然后将堆的大小减一，再对堆顶堆化。然后我们再对新的堆重复操作，直到堆大小为1。

每次堆化的时间为O(lgn)，建堆的时间为O(n)，我们一共会执行n次堆化，所以堆排序的时间复杂度为O(nlgn)。

优先队列

优先队列(priority queue)是堆的一种应用。

优先队列具有最高级先出 （first in, largest out）的行为特征

优先队列的一个应用是计算机系统的作业调度。每次都将执行优先级最高的作业。

最大优先队列支持以下几个操作：

1. insert 插入一个节点
2. maximum 取最大节点
3. extractMax 提取最大节点

insert

插入操作的步骤为：

1. 将新节点放到堆尾，然后找寻其父节点，如果父节点的值小于新节点，则交换节点。
2. 重复步骤一直到父节点的值大于新节点或者没有父节点。

另外，我们还可以用插入法建堆。

maximum

取堆数组的第一个元素

extractMax

其实在堆排序的时候有用到这个概念，就是将堆顶元素和堆尾元素互换，然后将堆大小-1，重新堆化堆顶。

算法题：第K大元素

给一堆数据，求出其中第K大的元素。
比如[1,2,3,3,4]其中第3大的元素是3，也就是重复的也计数。

这题我们可以用堆来解决，当然也可用暴力法，先排序，然后返回第K个元素，最快的时间复杂度为O(nlgn)。

我们知道数组的插入和删除是O(n)的，但是堆的插入删除只有O(lgn)。
如果我们维护一个大小为K的堆，那么这个堆就可以存储前K大的数或者前K小的数，然后我们再取堆顶，也就是第K大/小的树。因为插入删除的时间复杂度为O(lgk)，我们最多执行n次插入删除。用堆的时间复杂度就为O(nlgk)，空间复杂度为O(k)。

var findKthLargest = function (nums, k) {
  var heap = [];
  for (let i = 0; i < nums.length; i++) {
    const el = nums[i];

    if (heap.length === k && el > heap[0]) {
      heap[0] = el;
      minHeapify(heap, 1, k);
    }

    if (heap.length < k) {
      minHeapInsert(heap, el);
    }
  }

  return heap[0];
};

当然还有线性时间级的解法，主要通过分治思想，我们随机选取参照将数组划分为左右两边（左边比参照小），然后判断K的位置，再递归左或者右子数组。其算法时间复杂度为O(n)，最坏情况下为O(n^2)，但是划分是随机的，所以一般不会存在最坏情况。

文章源码