完全二叉树

满二叉树需要满足以下条件：

从第一层到倒数第二层每一层的结点树都达到了当前层所能达到的最大值。
最后一层的结点是从左到右排列的，不能存在跳跃

5. 堆 - 图1
上图中，黑色二叉树为完全二叉树，红色二叉树不是完全二叉树。

对于结点 n 来说：

索引 (n-1) / 2 的节点是它的父节点
索引 2 * n + 1 的节点是它的左子节点
索引 2 * n + 2 的节点是它的右子节点
完全二叉树的特例堆
堆分为大顶堆和小顶堆。
对于一个完全二叉树来说，它每个节点的值都不小于它左右孩子节点的值，这样的完全二叉树称为大顶堆。

对于一个完全二叉树来说，它每个节点的值都不大于它左右孩子节点的值，这样的完全二叉树称为小顶堆。

删除堆顶元素

插入元素

优先队列

数组中的第K个最大元素-215

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var findKthLargest = function(nums, k) {
    const heap = [];
    let n = 0;
    const len = nums.length;
    createHeap();
  updateHeap();
    return heap[0];

    function createHeap() {
        for (let i = 0; i < k; i++) {
            insert(nums[i]);
        }
    }
    function insert(x) {
        heap[n] = x;
        upHeap(0, n);
        n++;
    }
    function updateHeap() {
        for (let i = k; i < len; i++) {
            if (nums[i] > heap[0]) {
                heap[0] = nums[i];
                downHeap(0, k);
            }
        }
    }
    function upHeap(low, high) {
        let childIndex = high,
            parentIndex = Math.floor((childIndex - 1) / 2);
        while (parentIndex >= low) {
            if (heap[parentIndex] > heap[childIndex]) {
                let temp = heap[childIndex];
                heap[childIndex] = heap[parentIndex];
                heap[parentIndex] = temp;

                childIndex = parentIndex;
                parentIndex = Math.floor((childIndex - 1) / 2);
            } else break;
        }
    }
    function downHeap(low, high) {
        let parentIndex = low,
            childIndex = parentIndex * 2 + 1;
        while (childIndex <= high) {
            if (childIndex + 1 <= high && heap[childIndex + 1] < heap[childIndex]) childIndex += 1;
            if (heap[parentIndex] > heap[childIndex]) {
                let temp = heap[childIndex];
                heap[childIndex] = heap[parentIndex];
                heap[parentIndex] = temp;

                parentIndex = childIndex;
                childIndex = childIndex * 2 + 1;
            } else break;
        }
    }
};

封装 - 根据传惨返回大顶堆或者小顶堆的类
剑指 Offer 40. 最⼩的k个数
最后⼀块⽯头的重量-1046
```javascript 有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1] 输出：1 解释：先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

1 <= stones.length <= 30 1 <= stones[i] <= 1000

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/last-stone-weight 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：<br />将数组进行从大到小排序，计算索引 0 和索引 1 的差值并将结果的绝对值赋值给数组的第一个元素，删除索引 1 位置的元素。
```javascript
var lastStoneWeight = function (stones) {
  while (stones.length > 1) {
    stones.sort((a, b) => b - a)
    stones[0] = Math.abs(stones[0] - stones[1])
    stones.splice(1, 1)
  }
  return stones[0] ? stones[0] : 0
};

数据流中的第 K ⼤元素-703

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。


示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8


提示：
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
最多调用 add 方法 104 次
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var KthLargest = function(k, nums) {
  this.k = k;
  this.heap = new MinHeap();
  for(let node of nums) {
    this.add(node)
  }
};

/** 
* @param {number} val
* @return {number}
*/
KthLargest.prototype.add = function(val) {
  this.heap.push(val);
  if(this.heap.size() > this.k) this.heap.pop();
  return this.heap.peek();
};

class MinHeap {
  constructor() {
    this.data = [];
  }
  size() {
    return this.data.length;
  }
  peek() {
    return this.size() === 0 ? null : this.data[0]
  }

  push(val) {
    this.data.push(val);
    this.sifhtUp(val, this.size() - 1)
  }
  pop() {
    if(this.size() === 0) return null;
    let firstItem = this.data[0];
    let lastItem = this.data.pop();
    if(this.size() !== 0) {
      this.data[0] = lastItem;
      this.shiftDown(0)
    }
  }

  swap(i, j) {
    let temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j]= temp;
  }
  sifhtUp(val, i) {
    let index = i;
    while(index > 0) {
      const parentIndex = (index-1) >> 1;
      const parent = this.data[parentIndex];
      if(parent > val) {
        this.swap(index, parentIndex)
        index = parentIndex
      } else {
        break;
      }

    }
  }
  shiftDown(i) {
    let index = i;
    let n = this.size();
    while(index < n) {
      const c1 = 2*index + 1;
      const c2 = 2*index + 2;
      let min = index;
      if(c1 < n && this.data[c1] < this.data[min]) {
        min = c1
      }
      if(c2 < n && this.data[c2] < this.data[min]) {
        min = c2
      }
      if(min === index) {
        break
      }
      if(min !== index) {
        this.swap(index, min)
        index = min;
      }

    }
  }

}

查找和最⼩的K对数字-373

给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。



示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3 
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]


提示:

1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均为升序排列
1 <= k <= 1000


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

5. 堆

完全二叉树

完全二叉树的特例堆

删除堆顶元素

插入元素

优先队列

数组中的第K个最大元素-215

最后⼀块⽯头的重量-1046

数据流中的第 K ⼤元素-703

查找和最⼩的K对数字-373

数组中的第K个最⼤元素-215