堆

分类

• 最大堆
• 最小堆

在最大堆中，每个节点的值总是大于或等于其任意子节点的值
在最小堆中，每个节点的值总是小于或等于其任意子节点的值

堆的最大特点是最大值或最小值位于堆的顶部，只须要 O（1）的工夫就能够求出一个数据汇合的最大值或最小值

如果面试题需要求出一个动态数据汇合中的最大值或最小值，那么能够思考应用堆来解决问题。最小堆常常用来求取数据汇合中 k 个值最大的元素，而最大堆用来求取数据汇合中 k 个值最小的元素。

59. 数据流第 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);  }  size() {    return this.data.length;  }  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;      }    }  }  swap(index1, index2) {    [this.data[index1], this.data[index2]] = [      this.data[index2],      this.data[index1],    ];  }  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;  }  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;      }    }  }}

60. 呈现频率最高的 k 个数字

给定一个整数数组 nums 和一个整数 k ，请返回其中呈现频率前 k 高的元素。能够按 任意程序 返回答案。

/** * @param {number[]} nums * @param {number} k * @return {number[]} */var topKFrequent = function (nums, k) {  const map = new Map();  for (const n of nums) map.set(n, 1 + (map.get(n) || 0));  const arr = [];  for (const kv of map) arr.push(kv);  return arr    .sort((a, b) => b[1] - a[1])    .slice(0, k)    .map((a) => a[0]);};

61. 和最小的 k 个数对

题目：给定两个递增排序的整数数组，从两个数组中各取一个数字 u 和 v 组成一个数对（u，v），请找出和最小的 k 个数对。例如，输出两个数组[1，5，13，21]和[2，4，9，15]，和最小的 3 个数对为（1，2）、（1，4）和（2，5）。

• API 解法

/** * @param {number[]} nums1 * @param {number[]} nums2 * @param {number} k * @return {number[][]} */var kSmallestPairs = function (nums1, nums2, k) {  let res = [];  for (let i = 0; i < nums1.length; i++) {    for (let j = 0; j < nums2.length; j++) {      res.push([nums1[i], nums2[j]]);    }  }  return res    .sort((a, b) => {      return a[0] + a[1] - (b[0] + b[1]);    })    .slice(0, k);};

总结

堆又能够分成最大堆和最小堆。在最大堆中最大值总是位于堆顶，在最小堆中最小值总是位于堆顶。因而，在堆中只须要 O（1）的工夫就能失去堆中的最大值或最小值。堆常常用来解决在数据汇合中找出 k 个最大值或最小值相干的问题。通常用最大堆找出数据汇合中的 k 个最小值，用最小堆找出数据汇合中的 k 个最大值。

参考文章

• JS 刷 leetcode