LeetCode题解：347. 前 K 个高频元素，二叉堆，JavaScript，详细注释

[chencl1986]

原题连接：https://leetcode-cn.com/problems/top-k-frequent-elements/

解题思路：

1. 该题可使用堆解决，利用了堆能够快速插入和取出元素，并始终能够按要求排序的特点。
2. 创建一个大顶堆，元素按照出现的频次由大到小排序。
3. 遍历数组，统计所有元素出现的频次。
4. 将频次与元素一起存入堆中，所有元素都插入之后，都已按照要求排序。
5. 从堆中取出k次堆顶元素并返回，每次取出后堆还会保持由大到小的排序。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
 let result = []; // 存储结果
 let map = new Map(); // 用于统计元素出现频次
 // 使用堆将元素按出现频次从大到小排序
 let heap = new BinaryHeap((a, b) => b[1] - a[1]);

 // 遍历数组，统计元素出现的频次，并将其存入Map
 for (let i = 0; i < nums.length; i++) {
 map.has(nums[i])
 ? map.set(nums[i], map.get(nums[i]) + 1)
 : map.set(nums[i], 1);
 }

 // 将统计好的元素与频次取出，依次插入堆进行排序
 for (const element of map) {
 heap.insert(element);
 }

 // 从堆中依次取出k个元素，存入结果
 for (let i = 0; i < k; i++) {
 result.push(heap.deleteHead()[0]);
 }

 return result;
};

class BinaryHeap {
 constructor(compare) {
 this.data = []; // 使用数组存储堆
 this.compare = compare; // 堆元素的排序函数
 }

 // 获取堆的元素数量
 size() {
 return this.data.length;
 }

 // 向堆中插入多个元素
 insertMultiple(arr) {
 for (let i = 0; i < arr.length; i++) {
 this.insert(arr[i]);
 }
 }

 // 向堆插入元素
 insert(value) {
 this.insertAt(this.data.length, value);
 }

 // 将元素插入到index位置
 insertAt(index, value) {
 // 先将元素插入到指定的位置
 this.data[index] = value;
 let fatherIndex = index;
 // 对比当前节点与其父节点，如果当前节点更小就交换它们
 // Math.floor((index - 1) / 2)是父节点在数组中的索引
 while (
 index > 0 &&
 // 使用compare比较大小
 this.compare(
 value,
 this.data[(fatherIndex = Math.floor((index - 1) / 2))],
 ) < 0
 ) {
 // 将父节点移动到当前位置
 this.data[index] = this.data[fatherIndex];
 // 将插入的值移动到父节点位置
 this.data[fatherIndex] = value;
 // 更新索引为父节点索引，继续下一次循环
 index = fatherIndex;
 }
 }

 // 删除最大节点
 deleteHead() {
 return this.delete(0);
 }

 // 将指定位置的元素删除
 delete(index) {
 // 如果堆为空，则不进行删除操作
 if (this.data.length === 0) {
 return;
 }

 let value = this.data[index]; // 将要删除的元素缓存
 let parent = index; // 以当前元素为起始，向下整理堆

 // 不断向子节点整理堆，每次循环将子节点中经过compare方法对比后较大者与父节点调换
 while (parent < this.data.length) {
 let left = parent * 2 + 1; // 左子节点索引
 let right = parent * 2 + 2; // 右子节点索引

 // 没有左子节点，表示当前节点已经是最后一个节点
 if (left >= this.data.length) {
 break;
 }

 // 没有右子节点，则直接将左子节点提前到父节点即可
 // 该左子节点即为最后一个节点
 if (right >= this.data.length) {
 this.data[parent] = this.data[left];
 parent = left;
 break;
 }

 // 使用compare方法比较左右子节点的大小，更大的补到父节点
 if (this.compare(this.data[left], this.data[right]) < 0) {
 // 由于被删除的节点已保存，此处只需要将子节点复制到当前父节点即可
 this.data[parent] = this.data[left];
 // 完成移动后将父节点指针移动到子节点，供下一次整理使用
 parent = left;
 } else {
 this.data[parent] = this.data[right];
 parent = right;
 }
 }

 // 查看最后的空位是不是最后的叶子节点
 if (parent < this.data.length - 1) {
 // 如果还未整理到叶子节点，则继续向下整理
 this.insertAt(parent, this.data.pop());
 } else {
 // 当完成整理时，最后一个节点即为多于元素，直接弹出数组即可
 this.data.pop();
 }

 // 返回被删除的元素
 return value;
 }

 // 读取堆顶元素
 peek() {
 return this.data[0];
 }

 // 读取所有堆元素
 getData() {
 return this.data;
 }
}