堆

堆的概念

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

从上面的定义可以看出堆的本质就是一个完全二叉树，只不过它是用数组实现的而已。

分类

堆分为大顶推和小顶堆。

大（根）堆

大堆的性质是每个节点的值都大于它左右孩子节点的值，由此可以得出大堆的根节点是堆中最大的值。下面这个图就是一个大堆：

小（根）堆

小堆的性质是每个节点的值都小于它左右孩子节点的值，由此可以得出小堆的根节点是堆中最小的值。

注意：
堆的根节点不是最大值就是最小值，但是并不能确认它的其他节点的大小关系，我们并不能说根节点的左孩子一定比右孩子大或者右孩子比左孩子大。比如大顶堆中，根节点一定是最大值，但最小值我们只能确定它在叶子节点，但不能确认是哪一个。

思考：
在小堆中，第二小和第三小的值分别在第几层？

第二小的值在第二层，第三小的值在第二或者第三层。

堆和普通树的区别

内存占用

树中必须给左右子节点指针分配内存，而堆只需要一个数组存储即可，更节省内存。

搜索

堆的搜索性能比二叉树相对要差些，但是堆的主要目的是将最大值或者最小值放到顶部，从而进行插入、删除等操作。

性质

堆中某个节点的值总是不大于（或不小于）其父节点的值，也就是存在等于其父节点的值。
堆总是一个棵完全二叉树。
存储
如果我们需要将，假设 i (i 从零开始，因为数组从零开始的)是节点的索引，我们可以通过下面的公式计算出它的父节点和子节点在数组中的位置：
```
parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2
```
操作
尾部插入调整
调整步骤：尾部插入元素，如果大于父节点就和父节点交换位置。

如上，我们要将 13 插入进去，插入的结果如下：

头部弹出调整
调整步骤：头部弹出元素，用尾元素填充头部位置，然后和它的左右子节点对比，和大的那个子节点交换位置，依次执行这个操作，直到符合大堆的特点为止。

我们拿上面大堆的图举例，删除 12，将 12 从顶部删掉，将 3 从底部拿到顶部：

3 和它左右节点中较大的那个交换位置，这里和 11 交换位置，交换后的结果如下：

3 和它左右节点中较大的那个交换位置，这里和 9 交换位置，交换后的结果如下：

3 和它左右节点中较大的那个交换位置，这里和 5 交换位置，交换后的结果如下：

注意：
并不是每一个堆都是有序数组，要 将堆转换成有序数组，需要使用堆排序。

堆排序

规则：

将堆顶元素与堆尾元素交换
将此操作看作是堆顶元素弹出操作
按照头部弹出以后的策略调整堆

思考：

对如下堆进行堆排序，分别写出一次弹出后的数组和三次弹出后的数组：
[12, 11, 10, 6, 7, 9, 8, 5, 4, 3]

一次弹出后的数组：
[11, 7, 10, 6, 3, 9, 8, 5, 4, 12]
三次弹出后的数组：
[10, 7, 9, 6, 3, 4, 8, 5, 11, 12]
[9, 7, 8, 6, 3, 4, 5, 10, 11, 12]

应用

堆适合维护最值问题。

小堆的实现

// 小顶堆
class Heap {
  constructor(data = []) {
    this.data = data;
    this.heapify();
  }
  size() {
    return this.data.length;
  }
  // 创建时堆数据调整
  heapify() {
    if(this.size < 2) return;
    for(let i = 1; i < this.data.length; i++) {
      this.bubbleUp(i);
    }
  }

  // 尾部插入元素
  offer(val) {
    this.data.push(val);
    this.bubbleUp(this.size() - 1);
  }
  // 头部弹出
  poll() {
    if(!this.size()) return null;
    const res = this.data[0]; // 旧的头元素
    this.data[0] = this.data.pop(); // 将尾部元素，放到头的位置
    if(this.size()) { 
      this.bubbleDown(0); // 向下调整
    }
    return res;
  }
  // 交换元素
  swap(i, j) {
    if(i === j) return;
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }

  // 向上调整
  bubbleUp(index) {
    while(index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      // let parentIndex = (index - 1) >> 1;

      if(this.data[index] > this.data[parentIndex]) break;
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  // 向下调整
  bubbleDown(index) {
    let lastIndex = this.size() - 1;
    while( index < lastIndex) {
      let leftIndex = index * 2 + 1;
      let rightIndex = index * 2 + 2;

      // 比较当前值是否大于左右子节点的值
      let findIndex = index;
      if(this.data[leftIndex] < this.data[findIndex]) {
        findIndex = leftIndex;
      }
      if(this.data[rightIndex] < this.data[findIndex]) {
        findIndex = rightIndex;
      }
      if(index === findIndex) break;
      this.swap(index, findIndex);
      index = findIndex;
    }
  }
}

let arr = [10, 12, 1, 14, 6, 5, 8,15,2, 3, 9, 7];

const minHeap = new Heap(arr);
console.log(minHeap.poll());
console.log(minHeap.poll());
console.log(minHeap.data);
minHeap.offer(4);
minHeap.offer(16);
console.log(minHeap.data);

大堆的实现

class Heap {
    constructor(data=[]) {
        this.data = data;
        this.heapify();
    }
    size() {
        return this.data.length;
    }
    offer(val) {
        this.data.push(val);
        this.bubbleUp(this.size() - 1);
    }
    poll() {
        if (!this.size()) return null;
        const res = this.data[0];
        this.data[0] = this.data.pop();

        if (this.size()) this.bubbleDown(0);

        return res;
    }
    heapify() {
        if (this.size() < 2) return;
        for (let i = 1, len = this.size(); i < len; i++) {
            this.bubbleUp(i);
        }
    }
    swap(i, j) {
        [ this.data[i], this.data[j] ] = [ this.data[j], this.data[i] ];
    }
    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);

            if (this.data[index] < this.data[parentIndex]) break;

            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }
    bubbleDown(index) {
        const lastIndex = this.size() - 1;

        while (index < lastIndex) {
            const leftIndex = index * 2 + 1;
            const rightIndex = leftIndex + 1;
            let findIndex = index;

            if (this.data[leftIndex] > this.data[findIndex]) findIndex = leftIndex;
            if (this.data[rightIndex] > this.data[findIndex]) findIndex = rightIndex;

            if (index === findIndex) break;

            this.swap(index, findIndex);
            index = findIndex;
        }
    }
}

优先队列

堆是优先队列的一种实现方式。

分享题

总结：
大堆可以用来求解第k个最小的元素；小堆可以用来求解第k个大元素。

堆限制为 k , 则堆顶正好是第 k 小(大)的元素。

封装 - 根据传参返回大顶堆或者小顶堆的类

剑指 Offer 40. 最⼩的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。



示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]


限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000


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

方法一：对数组从小到大进行排序，然后取前 k 个。

var getLeastNumbers = function(arr, k) {
    return arr.sort((a,b)=>(a - b)).slice(0, k);
};

方法二：

class Heap {
    constructor(data=[]) {
        this.data = data;
        this.heapify();
    }
    size() {
        return this.data.length;
    }
    offer(val) {
        this.data.push(val);
        this.bubbleUp(this.size() - 1);
    }
    poll() {
        if (!this.size()) return null;
        const res = this.data[0];
        this.data[0] = this.data.pop();

        if (this.size()) this.bubbleDown(0);

        return res;
    }
    heapify() {
        if (this.size() < 2) return;
        for (let i = 1, len = this.size(); i < len; i++) {
            this.bubbleUp(i);
        }
    }
    swap(i, j) {
        [ this.data[i], this.data[j] ] = [ this.data[j], this.data[i] ];
    }
    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);

            if (this.data[index] < this.data[parentIndex]) break;

            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }
    bubbleDown(index) {
        const lastIndex = this.size() - 1;

        while (index < lastIndex) {
            const leftIndex = index * 2 + 1;
            const rightIndex = leftIndex + 1;
            let findIndex = index;

            if (this.data[leftIndex] > this.data[findIndex]) findIndex = leftIndex;
            if (this.data[rightIndex] > this.data[findIndex]) findIndex = rightIndex;

            if (index === findIndex) break;

            this.swap(index, findIndex);
            index = findIndex;
        }
    }
}
var getLeastNumbers = function(arr, k) {
    if (k == 0) return [];
    const maxHeap = new Heap();

    for (item of arr) {
        maxHeap.offer(item);
        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    }

    return maxHeap.data;
};

1046. 最后⼀块⽯头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：

var lastStoneWeight = function(stones) {
    const maxHeap = new MaxPriorityQueue();
    for (let i = 0; i < stones.length; i++) {
        maxHeap.enqueue('x', stones[i]);
    }
    while (maxHeap.size() > 1) {
        const a = maxHeap.dequeue()['priority'];
        const b = maxHeap.dequeue()['priority'];
        if (a > b) {
            maxHeap.enqueue('x', a - b);
        }
    }
    return maxHeap.isEmpty() ? 0 : maxHeap.dequeue()['priority'];
};

方法二：

var lastStoneWeight = function (stones) {
    if (stones.length == 2) {
        return Math.abs(stones[0] - stones[1])
    }
    if (stones.length == 1) {
        return stones[0];
    }
    stones.sort((a, b) => (a - b));
    if (stones[stones.length - 3] == 0) {
        return stones[stones.length - 1] - stones[stones.length - 2];
    }
    stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2];
    stones[stones.length - 2] = 0;
    return lastStoneWeight(stones);
};

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

设计一个找到数据流中第 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我们可以使用一个大小为 k 的优先队列来存储前 k 大的元素，其中优先队列的队头为队列中最小的元素，也就是第 k 大的元素。

在单次插入的操作中，我们首先将元素 val 加入到优先队列中。如果此时优先队列的大小大于 k，我们需要将优先队列的队头元素弹出，以保证优先队列的大小为 k。

复杂度分析

时间复杂度：

初始化时间复杂度为：O(nlogk) ，其中 nn 为初始化时 nums 的长度；

单次插入时间复杂度为：O(logk)。

空间复杂度：O(k)。需要使用优先队列存储前 k 大的元素。

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

KthLargest.prototype.add = function(val) {
    this.heap.offer(val);
    if (this.heap.size() > this.k) {
        this.heap.poll();
    }
    return this.heap.peek();
};

class MinHeap {
    constructor(data = []) {
        this.data = data;
        this.comparator = (a, b) => a - b;
        this.heapify();
    }

    heapify() {
        if (this.size() < 2) return;
        for (let i = 1; i < this.size(); i++) {
        this.bubbleUp(i);
        }
    }

    peek() {
        if (this.size() === 0) return null;
        return this.data[0];
    }

    offer(value) {
        this.data.push(value);
        this.bubbleUp(this.size() - 1);
    }

    poll() {
        if (this.size() === 0) {
            return null;
        }
        const result = this.data[0];
        const last = this.data.pop();
        if (this.size() !== 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return result;
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = (index - 1) >> 1;
            if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
                this.swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    bubbleDown(index) {
        const lastIndex = this.size() - 1;
        while (true) {
            const leftIndex = index * 2 + 1;
            const rightIndex = index * 2 + 2;
            let findIndex = index;
            if (
                leftIndex <= lastIndex &&
                this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
            ) {
                findIndex = leftIndex;
            }
            if (
                rightIndex <= lastIndex &&
                this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
            ) {
                findIndex = rightIndex;
            }
            if (index !== findIndex) {
                this.swap(index, findIndex);
                index = findIndex;
            } else {
                break;
            }
        }
    }

  swap(index1, index2) {
        [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
    }

    size() {
        return this.data.length;
    }
}

方法二：

function KthLargest(k, nums) {
    this.k = k;
    this.nums = nums;
}

KthLargest.prototype.add = function(val) {
    this.nums.push(val);
    this.nums.sort((a, b) => b - a);
    if (this.k === 1) return this.nums[0];
    return this.nums[this.k - 1];
};

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

给定两个以升序排列的整数数组 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 <= 104
-109 <= nums1[i], nums2[i] <= 109
nums1, nums2 均为升序排列
1 <= k <= 1000

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

var kSmallestPairs = function(nums1, nums2, k) {
    if (k > nums1.length * nums2.length ) {
        k = nums1.length * nums2.length
    }
    if (nums1.length == 0 || nums2.length == 0) {
        return [];
    }
    let steps = new Array(nums1.length);
    for (let i = 0; i < steps.length; i++) {
        steps[i] = 0;
    }
    let results = [];
    for (let i = 0; i < k; i++) {
        let min = Number.MAX_VALUE;
        let minStepIndex = 0;
        for (let j = 0; j < nums1.length; j++) {
            if (steps[j] < nums2.length && nums2[steps[j]] + nums1[j] < min) {
                min = nums2[steps[j]] + nums1[j];
                minStepIndex = j;
            }
        }
        results.push([nums1[minStepIndex], nums2[steps[minStepIndex]]]);
        steps[minStepIndex]++;
    }

    return results;
};

264.丑数II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。



示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。


提示：

1 <= n <= 1690


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

基本思路

根据丑数的定义，可以得出以下结论：

1 是最小的丑数
对于任何一个丑数，它与任意一个质因数（2、3、5）相乘结果仍然是丑数。
方法1-优先队列（最小堆）

将最小丑数 1 放入队列。
每次从队列取出最小值，分别乘以 2、3、5，将得到的结果放入队列。

重复步骤 2 ，第 n 次出队的值就是答案。 ```javascript class Heap { constructor(data = []) {

 this.data = data;
 this.heapify();

} size() {

 return this.data.length;

} heapify() {

 if (this.size < 2) return;
 for (let i = 1; i < this.data.length; i++) {
     this.bubbleUp(i);
 }

} offer(val) {

 this.data.push(val);
 this.data = [ ...new Set(this.data) ];
 this.bubbleUp(this.size() - 1);

} poll() {

 if (!this.size()) return null;
 const res = this.data[0];
 this.data[0] = this.data.pop();
 if (this.size()) {
     this.bubbleDown(0);
 }
 return res;

} swap(i, j) {

 if (i === j) return;
 [ this.data[i], this.data[j] ] = [ this.data[j], this.data[i] ];

}

bubbleUp(index) {

 while (index > 0) {
     let parentIndex = Math.floor((index - 1) / 2);

     if (this.data[index] > this.data[parentIndex]) break;
     this.swap(index, parentIndex);
     index = parentIndex;
 }

}

bubbleDown(index) {

 let lastIndex = this.size() - 1;
 while (index < lastIndex) {
     let leftIndex = index * 2 + 1;
     let rightIndex = index * 2 + 2;

     let findIndex = index;
     if (this.data[leftIndex] < this.data[findIndex]) {
         findIndex = leftIndex;
     }
     if (this.data[rightIndex] < this.data[findIndex]) {
         findIndex = rightIndex;
     }
     if (index === findIndex) break;
     this.swap(index, findIndex);
     index = findIndex;
 }

} }

const nums = [ 2, 3, 5 ];

<a name="JNDBl"></a>
### 方法2-数组
思路是和上面使用优先队列的接法是一样的，只不过是换成了数组而已。
```javascript
const nums = [ 2, 3, 5 ];

function nthUglyNumber(n) {
    let nums2 = [1];
    for (let i = 1; i <= n; i++) {
        const x = nums2.shift();
        if (i == n) return x;
        nums.forEach((item) => {
            const t = item * x;
            nums2.push(t);
            nums2 = [ ...new Set(nums2) ];
        });
        nums2.sort((a, b) => a - b);
    }
    return -1;
}

方法3-多路归并

首先我们来说下什么是多路归并？

多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。
                                                                                                                                                                                                        —— 百度百科

假设有 k 路数据流，流内部是有序的，且流间同为升序或者降序；
首先读取每个流的第一个数，如果已经结束就pass；
将有效的 k 个比较，选出最小的那路 mink 输出，读取 mink的下一个；

直到所有 k 路都结束；

function nthUglyNumber(n) {
  const ans = [];
  ans[1] = 1;
  // 由于三个有序序列都是由「已有丑数」*「质因数」而来
  // i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标（起始都指向 1）
  // idx 表示当前生成到 arr 的哪一位丑数
  for (let i2 = 1, i3 = 1, i5 = 1, idx = 2; idx <= n; idx++) {
      let a = ans[i2] * 2,
          b = ans[i3] * 3,
          c = ans[i5] * 5;
      // 将三个有序序列中的最小一位存入「已有丑数」序列，并将其下标后移
      let min = Math.min(a, Math.min(b, c));
      // 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ）
      if (min == a) i2++;
      if (min == b) i3++;
      if (min == c) i5++;
      console.log(i2, i3, i5);

      ans[idx] = min;
  }
  return ans[n];
}

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

``` 给定整数数组 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

<a name="J7Drh"></a>
### 方法1-数组排序
```javascript
var findKthLargest = function(nums, k) {
    return nums.sort((a, b) => b - a)[k - 1];
};

方法2-小顶堆

var findKthLargest = function(nums, k) {
    const heap = new MinHeap();
    for (let i = 0, len = nums.length; i < len; i++) {
        heap.offer(nums[i]);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.peek();
};

class MinHeap {
    constructor(data = []) {
        this.data = data;
        this.heapify();
    }
    size() {
        return this.data.length;
    }
    heapify() {
        if (this.size() < 2) return ;
        for (let i = 1, len = this.size(); i < len; i++) {
            this.bubbleUp(i)
        }
    }
    peek() {
        if (!this.size()) return null;
        return this.data[0];
    }
    offer(val) {
        this.data.push(val)
        this.bubbleUp(this.size() - 1);
    }
    poll() {
        if (!this.size()) return null;
        const res = this.data[0];
        this.data[0] = this.data.pop();
        if (this.size()) this.bubbleDown(0);
        return res;
    }
    swap(i, j) {
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
    }
    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.data[index] > this.data[parentIndex]) break;
            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }
    bubbleDown(index) {
        const lastIndex = this.size() - 1;
        while (index < lastIndex) {
            const leftIndex = index * 2 + 1;
            const rightIndex = leftIndex + 1;
            let findIndex = index;

            if (this.data[leftIndex] < this.data[findIndex]) findIndex = leftIndex;
            if (this.data[rightIndex] < this.data[findIndex]) findIndex = rightIndex;

            if (index === findIndex) break;
            this.swap(index, findIndex)
            index = findIndex;
        }
    }
}

参考

数据结构：堆（Heap）

算法

5.堆和优先队列

堆

堆的概念

分类

大（根）堆

小（根）堆

堆和普通树的区别

内存占用

搜索

性质

存储

操作

尾部插入调整

头部弹出调整

堆排序

应用

小堆的实现

大堆的实现

优先队列

分享题

封装 - 根据传参返回大顶堆或者小顶堆的类

剑指 Offer 40. 最⼩的k个数

1046. 最后⼀块⽯头的重量

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

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

264.丑数II

基本思路

方法1-优先队列（最小堆）

方法3-多路归并

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

方法2-小顶堆

参考