🐤五、leetcode经典题目剖析
接下来我们引用几道经典的 leetcode 算法，来巩固树和二叉树的知识。
1. leetcode215数组中的第K个最大元素（中等）
（1）题意
附上题目链接：leetcode215数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入输出示例：
- 输入:
[3,2,1,5,6,4]和k = 2 - 输出: 5
（2）解题思路
- 看到“第K个最大元素”。
- 考虑选择使用最小堆。
（3）解题步骤
- 构建一个最小堆，并以此把数组的值插入堆中。
- 当堆的容量超过K，就删除堆顶。
- 插入结束后，堆顶就是第K个最大元素。
（4）代码实现
依据上面我们构建的最小堆，接下来，我们用这个最小堆，来完成这道题。具体代码如下：
class MinHeap{ constructor(){ this.heap = []; } swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ return Math.floor((i - 1)/2); // 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[index]){ 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[index]){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] < this.heap[index]){ 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} */ let findKthLargest = function(nums, k){ const h = new MinHeap(); nums.forEach(n => { h.insert(n); if(h.size() > k){ h.pop(); } }); return h.peek(); } console.log(findKthLargest([3,2,1,5,6,4],2)); // 5 复制代码
2. leetcode347前K个高频元素（中等）
（1）题意
附上题目链接：leetcode347前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入输出示例：
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
（2）解题思路
- 字典解法：将字典转换为数组，且堆数组进行排序；
- 堆解法：构建一个最小堆，利用字典的键值关系，来记录元素出现的频率。
（3）代码实现
这道题我们用两种做法来实现，一种是字典解法，另外一种是堆解法。具体如下：
1）字典解法：
/** * @param {number[]} nums * @param {number} k * @return {number[]} */ // 字典解法 let topKFrequent1 = 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]); //使用map()方法，创建一个新数组，来存放前k个元素 return list.slice(0, k).map(n => n[0]); }; console.log(topKFrequent1([1, 1, 1, 2, 2, 3], 2)); // [1, 2] 复制代码
2）堆解法：
/** * @param {number[]} nums * @param {number} k * @return {number[]} */ // 堆解法 class MinHeap{ constructor(){ this.heap = []; } swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ return Math.floor((i - 1)/2); // 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; } } let topKFrequent2 = 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}); //判断当前堆的大小是否大于k值 if(h.size() > k){ h.pop(); } }); //返回值，对字典进行遍历，得到遍历后的键即为结果； //并通过map()方法创建一个新数组，才存放具体的值。 return h.heap.map(a => a.key); }; console.log(topKFrequent2([1, 1, 1, 2, 2, 3], 2)); // [2, 1] 复制代码
3. leetcode23合并K个排序链表（困难）
（1）题意
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入输出示例：
- 输入: 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 复制代码
（2）解题思路
- 新链表的下一个节点一定是k个链表头中的最小节点。
- 考虑选择使用最小堆。
（3）解题步骤
- 构建一个最小堆，并以此把链表头插入堆中。
- 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中。
- 等堆元素全部弹出，合并工作就完成了。
（4）代码实现
class MinHeap{ constructor(){ this.heap = []; } swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ return Math.floor((i - 1)/2); // 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].val > this.heap[index].val){ 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].val < this.heap[index].val){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } insert(val){ this.heap.push(val); this.shiftUp(this.heap.length - 1); } pop(){ // 如果堆只有一个元素，直接返回结果 if(this.size() === 1){ return this.heap.shift(); } const top = this.heap[0]; this.heap[0] = this.heap.pop(); this.shiftDown(0); return top; } peek(){ return this.heap[0]; } size(){ return this.heap.length; } } /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { //实例化一个空链表 const res = new ListNode(0); //定义一个p指针，指向空链表 let p = res; //实例化一个最小堆 const h = new MinHeap(); //将题目给的链表，挨个进行遍历 lists.forEach(l => { //遍历后的链表如果不为空，则插入最小堆当中 if(l){ h.insert(l); } }); //判断堆中是否有内容 while(h.size()){ //删除并返回堆顶 const n = h.pop(); //让p指针的next节点指向堆顶元素 p.next = n; //p.next的值赋给p指针 p = p.next; //如果堆顶元素有下一个节点，则将其插入堆中 if(n.next){ h.insert(n.next); } } return res.next; }; 复制代码
🐪六、结束语
学完这个数据结构的时候，想到上回看面经时有一道算法题。那道题目问到说，假设现在有一个文件，里面有很多个单词，请找出前10个出现频率最高的词汇。
当时我的心里想的是：遍历？但其实今天学完这个数据结构以后，回想起来，这道题的做法就是用最小堆来实现。
所以，堆在日常的应用中都是相通的，只要明白了其中的思想，间接地，也将可以应用到对应的各种场景当中。
到这里，关于堆在前端中的应用的讲解就结束啦！希望对大家有帮助~
如文章有误或有不理解的地方，欢迎小伙伴们评论区留言撒💬
