遵义市网站建设,阿里网站搭建,做公司的网站,可以做游戏广告的网站堆用于解决什么问题 堆排序#xff08;Heap Sort#xff09;#xff1a;优先队列#xff08;Priority Queue#xff09;#xff1a;图算法中的最短路径和最小生成树问题#xff1a;中位数查找#xff1a;合并K个有序数组#xff1a; 例子#xff1a;库存管理 III On时…堆用于解决什么问题 堆排序Heap Sort优先队列Priority Queue图算法中的最短路径和最小生成树问题中位数查找合并K个有序数组 例子库存管理 III On时间复杂度 原生API使用堆 计数排序 – 拿空间换时间 扩展1JavaScript slice 方法扩展2计数排序 堆可以分为 最小堆 和 最大堆 两种类型。
在最小堆中每个父节点的值都要小于或等于其子节点的值也就是说根节点是整个堆中的最小值。
而在最大堆中每个父节点的值都要大于或等于其子节点的值也就是说根节点是整个堆中的最大值。
下面举例说明堆的概念
最小堆
假设我们有一个包含以下元素的最小堆[5, 7, 10, 12, 15, 17, 20]
它的二叉树表示如下 5/ \7 10/ \ / \12 15 17 20在最小堆中根节点的值5是整个堆中的最小值。并且每个父节点的值都小于或等于其子节点的值。
最大堆
假设我们有一个包含以下元素的最大堆[30, 25, 20, 15, 10, 5]
它的二叉树表示如下 30/ \25 20/ \ /15 10 5在最大堆中根节点的值30是整个堆中的最大值。并且每个父节点的值都大于或等于其子节点的值。
堆可以应用于许多算法和数据结构例如堆排序、优先队列等。
更多详细内容请微信搜索“前端爱好者“ 戳我 查看 。
堆用于解决什么问题
堆Heap数据结构可以用于解决以下问题
堆排序Heap Sort
通过使用堆进行排序可以将一个无序数组转换为有序数组。堆排序的时间复杂度为O(nlogn)是一种高效的排序算法。
优先队列Priority Queue
优先队列是一种特殊的队列每个元素都有与之关联的优先级。堆可以实现优先队列的基本操作如插入元素、删除具有最高优先级的元素等。常见的应用包括任务调度、事件处理等。
图算法中的最短路径和最小生成树问题
在一些图算法中如Dijkstra算法和Prim算法需要找到最短路径或最小生成树。
堆可以用来维护待处理节点集合并在每次选择下一个节点时选择具有最小权重的节点。
中位数查找
在一系列数字中找到中位数是一种常见的问题。使用堆可以高效地找到中位数其中最小堆和最大堆可以分别存储较大和较小的一半数字。
合并K个有序数组
当需要合并多个有序数组时可以使用堆来提高效率。通过将每个数组的最小元素放入堆中然后每次弹出堆顶元素进行合并可以在时间复杂度为O(nlogk)的情况下完成合并操作。
这些只是堆应用的一些例子堆还可以用于解决其他许多问题特别是那些需要高效地查找最小或最大元素的场景。
例子库存管理 III O(n)时间复杂度
原生API
leetcode链接 https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
仓库管理员以数组 stock 形式记录商品库存表其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量返回 顺序不限。
示例 1
输入stock [2,5,7,4], cnt 1
输出[2]示例 2
输入stock [0,2,3,6], cnt 2
输出[0,2] 或 [2,0]提示
0 cnt stock.length 100000 stock[i] 10000思路:先排序然后取值
/*** param {number[]} stock* param {number} cnt* return {number[]}*/
var inventoryManagement function(stock, cnt) {// 先排序然后取值return stock.sort((a,b)a-b).slice(0,cnt)
};使用堆 计数排序 – 拿空间换时间
/*** param {number[]} stock* param {number} cnt* return {number[]}*/
var inventoryManagement function(stock, cnt) {// 先排序然后取值return countingSort(stock,cnt,10000)
};const countingSort (arr,k,length){// 将新开辟一个空间将输入的数据存储到空间let bucket new Array(length) let sortedIndex 0let arrLen arr.lengthlet bukectLength length// stock [2574] 原抬款组中下标对应的值 对应此处的下标for(let i 0; i arrLen;i){if(!bucket[arr[i]]){bucket[arr[i]] 0}bucket[arr[i]] } // bucket [0,0,1,0,1,1,0,1,]let res [] for (let j 0; j bukectLength;j){while(bucket[j]-- 0 sortedIndex k){res[sortedIndex] j}if(sortedIndex k){break}}return res
}扩展1JavaScript slice 方法
在JavaScript中slice()是一个数组方法用于从原始数组中提取指定范围的元素并返回一个新的数组。它不会修改原始数组而是返回一个浅拷贝。
slice()方法接受两个参数起始索引和结束索引可选。起始索引指定了截取的起始位置包含该索引对应的元素结束索引指定了截取的结束位置但不包含该索引对应的元素。
使用示例
const fruits [apple, banana, orange, grapefruit, kiwi];// 截取索引1到3之间的元素不包括索引3
const slicedFruits fruits.slice(1, 3);
console.log(slicedFruits); // 输出: [banana, orange]// 不传递结束索引则截取从起始索引到数组末尾的所有元素
const slicedFruits2 fruits.slice(2);
console.log(slicedFruits2); // 输出: [orange, grapefruit, kiwi]// 负数索引表示从数组末尾开始计算-2表示倒数第二个元素
const slicedFruits3 fruits.slice(-2);
console.log(slicedFruits3); // 输出: [grapefruit, kiwi]// 可以将slice()用于字符串
const str Hello, World!;
const slicedStr str.slice(7, 12);
console.log(slicedStr); // 输出: World注意事项
如果结束索引小于起始索引则返回一个空数组。原始数组的元素不会受到slice()方法影响它仅返回一个新的数组副本。slice()方法对字符串同样适用可以截取指定范围内的字符子串。
扩展2计数排序
计数排序Counting Sort是一种线性时间复杂度O(nk)的排序算法其中n是待排序元素的数量k是待排序元素的取值范围大小。计数排序适用于排序范围较小的整数数组。
计数排序的基本思想是统计每个元素出现的次数然后根据统计信息将元素放回正确的位置。它使用一个额外的计数数组来存储每个元素的出现次数然后通过累加计数数组中的值确定每个元素在排好序的数组中的最终位置。
下面是计数排序的示例步骤 统计每个元素出现的次数遍历待排序数组对每个元素进行计数并将计数结果存储在对应索引位置的计数数组中。 累加计数数组对计数数组进行累加操作每个位置的值等于前面所有位置的值之和这样可以确定每个元素在排序后数组中的最终位置。 排序创建一个与待排序数组相同大小的临时数组遍历待排序数组根据计数数组中的值确定每个元素在临时数组中的位置并将元素放置到临时数组中。 将临时数组中的元素复制回原始数组将临时数组中的元素按顺序复制回原始数组即完成排序。
以下是一个计数排序的示例代码使用JavaScript
function countingSort(arr) {const len arr.length;if (len 1) {return arr;}// 找出待排序数组中的最大值let max arr[0];for (let i 1; i len; i) {if (arr[i] max) {max arr[i];}}// 创建计数数组并统计每个元素的出现次数const countArray new Array(max 1).fill(0);for (let i 0; i len; i) {countArray[arr[i]];}// 累加计数数组for (let i 1; i max; i) {countArray[i] countArray[i - 1];}// 创建临时数组存储排序结果const tempArray new Array(len);// 排序for (let i len - 1; i 0; i--) {const value arr[i];const index countArray[value] - 1;tempArray[index] value;countArray[value]--;}// 将临时数组复制回原始数组for (let i 0; i len; i) {arr[i] tempArray[i];}return arr;
}// 使用示例
const array [5, 8, 2, 1, 9, 3, 5];
const sortedArray countingSort(array);
console.log(sortedArray); // 输出: [1, 2, 3, 5, 5, 8, 9]计数排序的优势在于它不是基于比较的排序算法因此在某些情况下它可以比其他排序算法更快。但是计数排序的缺点是它对输入数据的取值范围有一定要求并且需要额外的空间来存储计数数组和临时数组。
