温州营销网站公司哪家好,网页游戏平台app,网站建设的同义词,广州做网站哪家好一文了解堆在前端中的应用⚡序言#x1f998;一、堆是什么#xff1f;#x1f425;二、JS中的堆#x1f41d;三、堆的应用#x1f408;四、构建一个最小堆1. 定义2. 方法3. 用js代码实现最小堆#xff08;1#xff09;初始化一个堆#xff08;2#xff09;交换位置swa… 一文了解堆在前端中的应用⚡序言一、堆是什么二、JS中的堆三、堆的应用四、构建一个最小堆1. 定义2. 方法3. 用js代码实现最小堆1初始化一个堆2交换位置swap()3获取父节点的位置getParentIndex()4获取左侧子节点的位置getLeftIndex()5获取右侧子节点的位置getRightIndex()6进行上移操作shiftUp()7进行下移操作shiftDown()8插入节点的值insert()9删除堆顶操作pop()10获取堆顶的值peek()11获取堆的大小size()12结果展示五、leetcode经典题目剖析1. leetcode215数组中的第K个最大元素中等2. leetcode347前K个高频元素中等3. leetcode23合并K个排序链表困难六、结束语彩蛋 One More Thing(往期推荐(番外篇⚡序言
我们都知道树是一个数据结构但可能很少听到堆这个数据结构。其实堆就是一种特殊的完全二叉树。而对于前端来说我们通常了解最大堆和最小堆也经常用最大堆和最小堆来解决各种问题。比如数组中的第K个最大元素、文档中前K个高频元素等等。
在下面的这篇文章中将讲解堆的基础知识并手动地用 js 来构建一个最小堆同时剖析几道经典的 leetcode 算法题。
接下来开始进入本文的讲解~
一、堆是什么
堆是一种特殊的 完全二叉树 完全二叉树意味着每个节点都有两个孩子节点。最大堆所有的节点都 大于等于≥ 它的子节点最小堆所有的节点都 小于等于≤ 它的子节点。
二、JS中的堆
JS 通常用数组来表示堆。左侧节点的位置是 2*index1 。右侧节点的位置是 2*index2 。父节点位置是 (index - 1) / 2 。
三、堆的应用
堆能够高效、快速地找出最大值和最小值时间复杂度 O(1) 。在开发中有时候我们可能会想要找到一个数组中的最大或者最小元素而堆就可以找出第K个最大小元素。
四、构建一个最小堆
1. 定义
从上面的小知识中我们可以了解到对于最小堆来说它的所有节点都小于等于它的子节点。接下来我们来看堆这个数据结构的一些常见实现方法。
2. 方法
方法含义swap()交换两个节点的位置getParentIndex()获取父节点的位置getLeftIndex()获取左侧子节点的位置getRightIndex()获取右侧子节点的位置shiftUp()进行上移操作shiftDown()进行下移操作insert()插入节点的值pop()删除堆顶操作peek()获取堆顶的值size()获取堆的大小
3. 用js代码实现最小堆
1初始化一个堆
首先我们需要先来定义一个空数组这个数组用来存放一个堆。具体代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}
}2交换位置swap()
初始化完一个堆之后如果想要实现上下移操作我们时不时的还需要对两个节点进行位置交换。那么我们再来写一个交换节点位置的方法。具体代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置swap(i1, i2){const temp this.heap[i1];this.heap[i1] this.heap[i2];this.heap[i2] temp;}
}3获取父节点的位置getParentIndex()
上面我们讲到父节点的位置是在 (index - 1) / 2 。 因此我们需要传入当前节点的值索引 index 来进行一个地板除操作获取具体的父节点位置。具体代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置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;}
}4获取左侧子节点的位置getLeftIndex()
对于左侧子节点来说其索引为 2 * index 1 也就是说它是 当前节点的索引值的2倍 1 。具体实现代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置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;}//获取左侧子节点i为当前节点的索引getLeftIndex(i){return i * 2 1;}
}5获取右侧子节点的位置getRightIndex()
对于右侧子节点来说其索引为 2 * index 2 也就是说它是 当前节点的索引值的2倍 2 。具体实现代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置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;}//获取左侧子节点i为当前节点的索引getLeftIndex(i){return i * 2 1;}//获取右侧子节点i为当前节点的索引getRightIndex(i){return i * 2 2;}
}6进行上移操作shiftUp()
上面我们实现了获取父节点等获取各种索引的操作现在我们来实现上移操作。
对于上移操作来说实现思路如下
先判断当前节点的位置是否在堆的顶点处如果是则不进行上移操作如果否则继续进行比较获取父节点的位置索引获取索引的目的是为了获取该索引的具体值将当前节点的值与父节点的值进行对比如果父节点的值大于当前节点的值则进行上移操作递归进行上移操作直到到达堆顶为止。
下面给出具体的代码实现方法
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置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;}//shiftUp进行上移操作shiftUp(index){//如果在堆的顶点处则不进行上移操作直接返回结果if(index 0){return;}//获取父节点(即获取当前节点的父节点的值且每个节点的父节点只有一个)const parentIndex this.getParentIndex(index);//判断如果堆的父节点如果大于子节点则进行位置交换if(this.heap[parentIndex] this.heap[index]){this.swap(parentIndex, index);//交换完成之后继续递归进行上移操作this.shinftUp(parentIndex);}}
}7进行下移操作shiftDown()
对于下移操作来说实现思路如下
先获取左右侧节点将左侧子节点与当前节点进行比较如果左侧子节点比当前节点小则进行位置交换之后将交换完的节点继续进行比较左侧节点比较完之后接下来比较右侧节点将右侧子节点与当前节点进行比较如果右侧子节点比当前节点小则进行位置交换之后将交换完的节点继续进行比较如此循环操作直到最后一个节点为止。
下面给出具体的代码实现方法
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置swap(i1, i2){const temp this.heap[i1];this.heap[i1] this.heap[i2];this.heap[i2] temp;}//获取左侧子节点i为当前节点的索引getLeftIndex(i){return i * 2 1;}//获取右侧子节点i为当前节点的索引getRightIndex(i){return i * 2 2;}// 进行下移操作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);}}
}8插入节点的值insert()
对于插入节点操作来说实现思路如下
将值插入堆的底部即数组的尾部。然后上移将这个值和它的父节点进行交换直到父节点小于等于这个插入的值。大小为k的堆中插入元素的时间复杂度为 O(logK) 。
下面给出具体的代码实现方法
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置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;}//shiftUp进行上移操作shiftUp(index){//如果在堆的顶点处则不进行上移操作直接返回结果if(index 0){return;}//获取父节点(即获取当前节点的父节点的值且每个节点的父节点只有一个)const parentIndex this.getParentIndex(index);//判断如果堆的父节点如果大于子节点则进行位置交换if(this.heap[parentIndex] this.heap[index]){this.swap(parentIndex, index);//交换完成之后继续递归进行上移操作this.shinftUp(parentIndex);}}//插入结点值的操作value为被插入的值insert(value){//把新的值放到数组的最后一位this.heap.push(value);//将值进行上移操作this.shiftUp(this.heap.length - 1);}
}9删除堆顶操作pop()
对于删除堆顶操作来说实现思路如下
用数组尾部元素替换堆顶因为直接删除堆顶会破坏堆结构。然后下移将新堆顶和它的子节点进行交换直到子节点大于等于这个新堆顶。大小为 k 的堆中删除堆顶的时间复杂度为 O(logK) 。
下面给出具体的代码实现方法
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//交换节点i1和i2之间的位置swap(i1, i2){const temp this.heap[i1];this.heap[i1] this.heap[i2];this.heap[i2] temp;}//获取左侧子节点i为当前节点的索引getLeftIndex(i){return i * 2 1;}//获取右侧子节点i为当前节点的索引getRightIndex(i){return i * 2 2;}// 进行下移操作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);}}//删除堆顶操作pop(){//将尾部的值赋值给堆顶this.heap[0] this.heap.pop();//进行下移操作this.shiftDown(0);}
}10获取堆顶的值peek()
对于获取堆顶的值操作来说实现思路较为简单也就是返回数组的头部即可获取堆顶的值。具体实现代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//获取堆顶的值peek(){return this.heap[0];}
}11获取堆的大小size()
对于获取堆的大小操作来说实现思路其实就是获取整个堆的长度也就是返回数组的长度。具体实现代码如下
class MinHeap{//创建一个构造器存放一个堆constructor(){this.heap [];}//获取堆的大小size(){return this.heap.length;}
}12结果展示
完成上面的操作以后接下来我们来对写一组测试用例演示具体的结果。具体代码如下
const h new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();
console.log(h); // MinHeap { heap: [ 2, 4, 3 ] }
h.peek();
h.size();
console.log(h.peek()); // 2
console.log(h.size()); // 3五、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)); // 52. 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-62解题思路
新链表的下一个节点一定是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 (valundefined ? 0 : val)* this.next (nextundefined ? 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个出现频率最高的词汇。
当时我的心里想的是遍历但其实今天学完这个数据结构以后回想起来这道题的做法就是用最小堆来实现。
所以堆在日常的应用中都是相通的只要明白了其中的思想间接地也将可以应用到对应的各种场景当中。
到这里关于堆在前端中的应用的讲解就结束啦希望对大家有帮助~
如文章有误或有不理解的地方欢迎小伙伴们评论区留言撒
彩蛋 One More Thing
(往期推荐
栈栈在前端中的应用顺便再了解下深拷贝和浅拷贝
队列详解队列在前端的应用深剖JS中的事件循环Eventloop再了解微任务和宏任务
链表详解链表在前端的应用顺便再弄懂原型和原型链
字典和集合ES6的Set和Map你都知道吗一文了解集合和字典在前端中的应用
树一文了解树在前端中的应用掌握数据结构中树的生命线
图太平洋大西洋水流问题如何解决一文了解图在前端中的应用
动态规则和分而治之算法一文了解分而治之和动态规则算法在前端中的应用
贪心算法和回溯算法一文了解贪心算法和回溯算法在前端中的应用
(番外篇 关注公众号星期一研究室第一时间关注学习干货更多精选专栏待你解锁~如果这篇文章对你有用记得留个脚印jio再走哦~以上就是本文的全部内容我们下期见
