• 堆是一种特殊的完全二叉树。
  • 所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。

最大堆：
image.png
最小堆：
image.png
JS中的堆：

  • JS中通常用数组表示堆。
  • 左侧子节点的位置是 2*index + 1
  • 右侧子节点的位置是 2*index + 2
  • 父节点位置是 (index-1)/2

image.png

堆的应用

  • 堆能高效、快速地找出最大值和最小值。
  • 时间复杂度O(1)。
  • 找出第K个最大(小)元素。

第k个最大元素

  • 构建一个最小堆，并将元素依次插入堆中。
  • 当堆的容量超过k时，就删除堆顶。
  • 插入结束后，堆顶就是第k个最大元素。

实现最小堆类

实现步骤：

  1. 在类里，声明一个数组，用来装元素。
  2. 主要方法：插入、删除堆顶、获取堆顶、获取堆大小。

插入

  • 把值插入堆的底部，即数组的尾部。
  • 然后上移：将这个值和他的父节点进行交换，直到父节点小于等于这个插入的值。
  • 大小为k的堆中插入元素的时间复杂度为O(log k)

删除堆顶

  • 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
  • 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶。
  • 大小为k的堆中删除堆顶的时间复杂度为O(log k)

获取堆顶和堆的大小

  • 获取堆顶：返回数组的头部
  • 获取堆的大小：返回数组的长度

构建一个最小堆的类：

  1. class MinHeap {
  2.     constructor() {
  3.         this.heap = [];
  4.     }
  5.     swap(i1, i2) {
  6.         const tmp = this.heap[i1];
  7.         this.heap[i1] = this.heap[i2];
  8.         this.heap[i2] = tmp;
  9.     }
  10.     getParentIndex(i) {
  11.         return (i-1) >> 1;
  12.     }
  13.     getLeftIndex(i) {
  14.         return i * 2 + 1;
  15.     }
  16.     getRightIndex(i) {
  17.         return i * 2 + 2;
  18.     }
  19.   //上移操作
  20.     shiftUp(index) {
  21.         if( index == 0) { return ;}
  22.         const parentIndex = this.getParentIndex(index);
  23.         if(this.heap[parentIndex] > this.heap[index]) {
  24.             this.swap(parentIndex, index);
  25.             this.shiftUp(parentIndex);
  26.         }
  27.     }
  28.   //下移操作
  29.     shiftDown(index) {
  30.         const leftIndex = this.getLeftIndex(index);
  31.         const rightIndex = this.getRightIndex(index);
  32.         if(this.heap[leftIndex] < this.heap[index]){
  33.             this.swap(leftIndex, index);
  34.             this.shiftDown(leftIndex);
  35.         }
  36.         if(this.heap[rightIndex] < this.heap[index]){
  37.             this.swap(rightIndex, index);
  38.             this.shiftDown(rightIndex);
  39.         }
  40.     }
  41.      insert (value) {
  42.         this.heap.push(value);
  43.         this.shiftUp(this.heap.length - 1);
  44.      }
  46.      pop() {
  47.          this.heap[0] = this.heap.pop();
  48.          this.shiftDown(0)
  49.      }
  51.      peek() {
  52.         return this.heap[0];
  53.      }
  55.      size() {
  56.          return this.heap.length;
  57.      }
  59. }
  61. const h = new MinHeap();
  62. h.insert(3)
  63. h.insert(2)
  64. h.insert(1)
  65. h.pop()

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

解题思路：

  • 看到“第k个最大元素”。
  • 考虑使用最小堆。

解题步骤：

  • 构建一个最小堆，并依次把数组的值插入堆中。
  • 当堆的容量超过k，就删除堆顶。

  • 插入结束后，堆顶就是第k个最大元素。

    var findKthLargest = function(nums, k) {
  const h = new MinHeap();
  nums.forEach(n => {
      h.insert(n);
      if(h.size() > k) {
          h.pop();
      }
  })

  return h.peek();
};

    347 前 K 个高频元素

    var topKFrequent = function(nums, k) {
  const map = new Map();
  nums.forEach(n=>{
      map.set(n, map.has(n) ? map.get(n)+1 : 1)
  })
  const list = Array.from(map).sort((a,b)=> b[1]-a[1]);

  return list.slice(0, k).map(n => n[0])
};

    堆解法： ```javascript class MinHeap { constructor() {

      this.heap = [];

    } swap(i1, i2) {

      const tmp = this.heap[i1];
  this.heap[i1] = this.heap[i2];
  this.heap[i2] = tmp;

    } getParentIndex(i) {

      return (i-1) >> 1;

    } getLeftIndex(i) {

      return i * 2 + 1;

    } getRightIndex(i) {

      return i * 2 + 2;

    } //上移操作 shiftUp(index) {

      if( index == 0) { return ;}
  const parentIndex = this.getParentIndex(index);
  if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
  }

    } //下移操作 shiftDown(index) {

      const leftIndex = this.getLeftIndex(index);
  const rightIndex = this.getRightIndex(index);
  if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
  }
  if(this.heap[rightIndex] && this.heap[rightIndex].value <  this.heap[index].value){
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
  }

    } insert (value) {

      this.heap.push(value);
  this.shiftUp(this.heap.length - 1);

    }

    pop() {

       this.heap[0] = this.heap.pop();
   this.shiftDown(0)

    }

    peek() {

      return this.heap[0];

    }

    size() {

       return this.heap.length;

    }

}

/**

  • @param {number[]} nums
  • @param {number} k

  • @return {number[]} */ var topKFrequent = function(nums, k) { const map = new Map(); nums.forEach(n=>{

     map.set(n, map.has(n) ? map.get(n)+1 : 1)

    }) const h = new MinHeap(); map.forEach((value, key)=>{

     h.insert({value, key});
 if(h.size() > k) {
     h.pop();
 }

    });

    return h.heap.map(a => a.key) }; ```

23 合并K个升序链表

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

解题思路：

  • 新链表的下一个节点一定是k个链表头中的最小节点。
  • 考虑选择使用最小堆

解题步骤：

  • 构建一个最小堆，并一次把链表头插入堆中。
  • 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中。
  • 等堆元素全部弹出，合并工作就完成了。
var mergeKLists = function(lists) {
    const res = new ListNode(0);
    let p = res;
    const h = new MinHeap();
    lists.forEach(l => {
       if(l) h.insert(l);
    });
    while(h.size() > 0) {
        const n = h.pop();
        p.next = n;
        p = p.next;
        if(n.next) h.insert(n.next);
    }
    return res.next; 
};