React 优先级队列小顶堆的简单实现

news/2024/6/15 16:41:44/文章来源:https://blog.csdn.net/qq1123642601/article/details/137292538

这篇文章是博主最近在阅读 React 源码过程中关于优先级队列数据结构实现的一些提炼

我们都知道 React Schedule 中的优先级队列,本身采用小顶堆来保证队列的第一个任务是优先级最高的,并且获取优先级最高的任务的时间复杂度为 O(1)。所以今天写了个简化版的小顶堆的实现,方便大家理解。

首先优先级队列有两种操作,一种是添加任务,另外一种是移除优先级最高的任务(第一个任务)

const heap = [];
// 添加任务
const push = (val) => {// 先将任务添加到队列中heap.push(val); // 对当前任务节点进行向上调整,具体实现看后面siftUp(heap, val, heap.length);
};// 移除优先级最高的任务
const pop = () => {// 拿到最后一个任务放到第一个任务来的位置上来const last = heap.pop();heap[0] = last;// 对当前任务节点进行向下调整,具体实现看后面siftDown(heap, last, 0);
};// 获取优先级最高的任务
const peek = () => {return heap.length ? heap[0] : null;
};

当我们往队列中去添加新的任务的时候,那么这个任务是肯定会在队尾。但由于小顶堆的特性,我们需要保证第一个任务优先级要最高,所以需要拿新任务和他的所有父节点去进行对比。

const siftUp = (heap, node, i) => {// 需要把节点下标记录下来,let index = i - 1;while (index > 0) {// 拿到 push 进来的节点的父节点const parentIndex = index >>> 1; // 等价于 Math.floor((index - 1) / 2)const parent = heap[parentIndex];if (parent > node) {// 如果父节点大于当前节点,说明当前节点需要和父节点交换位置heap[parentIndex] = node;heap[index] = parent;index = parentIndex;} else {return;}}
};

移除操作也是同理,移除一个高优先级任务之后,会把队尾的任务提高最顶部来,为了保证小顶堆的特性,所以需要拿这个任务和其子节点进行对比。

const siftDown = (heap, node, i) => {let index = i; // 当前需要处理节点的下标const idx = heap.length >>> 1; // 拿到最深的非叶子结点的下标,由于小顶堆的特性,不需要到叶子节点去while (index < idx) {let leftIndex = 2 * index + 1;let left = heap[leftIndex];let rightIndex = leftIndex + 1;let right = heap[rightIndex];// 如果当前节点,比左子节点要大,说明需要调整if (node > left) {// 如果左子节点比右子节点要大,说明右子节点是目前最小的,应该和当前节点交换位置if (left > right) {heap[rightIndex] = node;heap[index] = right;index = rightIndex;} else {// 如果左子节点比右子节点要小,说明左子节点是目前最小的,应该和当前节点交换位置heap[leftIndex] = node;heap[index] = left;index = leftIndex;}} else if (node > right) {// 如果当前节点,比右子节点要大,说明需要交换位置heap[rightIndex] = node;heap[index] = right;index = rightIndex;} else {return;}}
};

写完了上面的代码之后,我们可以测一下

push(5);
push(7);
push(10);
push(8);
push(2);
push(6);
console.log(heap); // [ 2, 5, 6, 8, 10, 7 ]pop();
console.log(heap); // [ 5, 7, 6, 8, 10 ]

完整的代码如下:

const heap = [];// 添加任务
const push = (val) => {// 先将任务添加到队列中heap.push(val); // 对当前任务节点进行向上调整,具体实现看后面siftUp(heap, val, heap.length);
};// 移除优先级最高的任务
const pop = () => {// 拿到最后一个任务放到第一个任务来的位置上来const last = heap.pop();heap[0] = last;// 对当前任务节点进行向下调整,具体实现看后面siftDown(heap, last, 0);
};// 获取优先级最高的任务
const peek = () => {return heap.length ? heap[0] : null;
};const siftUp = (heap, node, i) => {// 需要把节点下标记录下来,let index = i - 1;while (index > 0) {// 拿到 push 进来的节点的父节点const parentIndex = index >>> 1; // 等价于 Math.floor((index - 1) / 2)const parent = heap[parentIndex];if (parent > node) {// 如果父节点大于当前节点,说明当前节点需要和父节点交换位置heap[parentIndex] = node;heap[index] = parent;index = parentIndex;} else {return;}}
};const siftDown = (heap, node, i) => {let index = i; // 当前需要处理节点的下标const idx = heap.length >>> 1; // 拿到最深的非叶子结点的下标while (index < idx) {let leftIndex = 2 * index + 1;let left = heap[leftIndex];let rightIndex = leftIndex + 1;let right = heap[rightIndex];// 如果当前节点,比左子节点要大,说明需要调整if (node > left) {// 如果左子节点比右子节点要大,说明右子节点是目前最小的,应该和当前节点交换位置if (left > right) {heap[rightIndex] = node;heap[index] = right;index = rightIndex;} else {// 如果左子节点比右子节点要小,说明左子节点是目前最小的,应该和当前节点交换位置heap[leftIndex] = node;heap[index] = left;index = leftIndex;}} else if (node > right) {// 如果当前节点,比右子节点要大,说明需要交换位置heap[rightIndex] = node;heap[index] = right;index = rightIndex;} else {return;}}
};push(5);
push(7);
push(10);
push(8);
push(2);
push(6);
console.log(heap);pop();
console.log(heap);

参考:React 源码 - 最小堆实现

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034300.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于java+SpringBoot+Vue的时间管理系统设计与实现

基于javaSpringBootVue的时间管理系统设计与实现 开发语言: Java 数据库: MySQL技术: SpringBoot MyBatis工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 后台展示 系统简介 整体功能包含&#xff1a; 时间管理系统是一个基于Internet的应用程序&#xff0c;旨在…

JavaBean是什么?

Bean的本意为豌豆、子实&#xff0c;在这里引申为一种实体。JavaBean 是一种JAVA语言写成的可重用组件。为写成JavaBean&#xff0c;类必须是具体的和公共的&#xff0c;并且具有无参数的构造器。JavaBean 通过提供符合一致性设计模式的公共方法将内部域暴露成员属性&#xff0…

【unity】unity安装及路线图

学习路线图 二、有关unity的下载 由于unity公司是在国外&#xff0c;所以.com版&#xff08;https://developer.unity.cn/&#xff09;不一定稳定&#xff0c;学习时推荐从.cn国内版&#xff08;https://developer.unity.cn/&#xff09;前往下载&#xff0c;但是后期仍需回…

React Native框架开发APP,安装免费的图标库(react-native-vector-icons)并使用详解

一、安装图标库 要使用免费的图标库&#xff0c;你可以使用 React Native Vector Icons 库。 首先&#xff0c;确保你已经安装了 react-native-vector-icons&#xff1a; npm install --save react-native-vector-iconsnpm install --save-dev types/react-native-vector-ic…

最新AI工具系统ChatGPT网站运营源码SparkAi系统V6.0版本,GPTs应用、AI绘画、AI换脸、垫图混图、Suno-v3-AI音乐生成大模型全支持

一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持GPT…

bugku-web-cookies

进来以后看到一个巨长的字符串 源码同样 rfrgrggggggoaihegfdiofi48ty598whrefeoiahfeiafehbaienvdivrbgtubgtrsgbvaerubaufibryrfrgrggggggoaihegfdiofi48ty598whrefeoiahfeiafehbaienvdivrbgtubgtrsgbvaerubaufibryrfrgrggggggoaihegfdiofi48ty598whrefeoiahfeiafehbaienvdi…

景顺长城:《重塑与创造——2024 ai+洞察报告》

近期&#xff0c;景顺长城发布了《重塑与创造——2024 ai洞察报告》,报告深入探讨了人工智能&#xff08;AI&#xff09;产业的发展现状、未来趋势以及对各行业的潜在影响。报告认为&#xff0c;AI产业发展是多层次、多浪潮的&#xff0c;目前我们处于第二阶段但未来将持续伴随…

Windows 11 专业版 23H2 Docker Desktop 下载 安装 配置 使用

博文目录 文章目录 Docker Desktop准备系统要求 (WSL 2 backend)在 Windows 上打开 WSL 2 功能先决条件开启 WSL 2 WSL下载安装启动配置使用镜像 Image卷积 Volumes容器 Containers 命令RedisMySQLPostGreSQL Docker Desktop Overview of Docker Desktop Docker Desktop 疑难解…

vscode安装

&#x1f308;个人主页&#xff1a;Rookie Maker &#x1f3c6;&#x1f3c6;关注博主&#xff0c;随时获取更多关于IT的优质内容&#xff01;&#x1f3c6;&#x1f3c6; &#x1f600;欢迎来到小田代码世界~ &#x1f601; 喜欢的小伙伴记得一键三连哦 ૮(˶ᵔ ᵕ ᵔ˶)ა …

coooooode

1.局部变量在栈上初始化&#xff1a;.stack .const 2.未初始化的全局变量在.bss区 3.初始化的全局变量在.data和.const区

【经典算法】LeetCode14:最长公共前缀(Java/C/Python3实现含注释说明,Easy)

最长公共前缀 题目思路及实现方式一&#xff1a;横向扫描思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式二&#xff1a;纵向扫描思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式三&#xff1a;分治思路代码实现Java版本C语言版本Python3版本 复杂度分析…

【Go】八、常用字符串函数与时间函数

文章目录 1、字符串常用的函数2、常用的时间函数3、内置函数 1、字符串常用的函数 核心包strings 求字符串长度&#xff0c;按字节&#xff08;len函数内置&#xff0c;不用导包&#xff09; 字符串遍历 //转切片 r:[]rune(str)字符串与整数的互转 查找是否包含子字符串 re…

Nginx-记

Nginx是一个高性能的web服务器和反向代理服务器&#xff0c;用于HTTP、HTTPS、SMTP、POP3和IMAP协议。因它的稳定性、丰富的功能集、示例配置文件和低系统资源的消耗而闻名。 &#xff08;1&#xff09;更快 这表现在两个方面&#xff1a;一方面&#xff0c;在正常情况下&…

elementui日期时间选择框自定义组件

1.需求场景 业务中需要&#xff0c;日期选择框方便客户对日期的选择&#xff08;比如近5天&#xff0c;本周&#xff0c;本月&#xff0c;本年等等&#xff09;&#xff0c;并按小时展示。 2.组件代码MyDateTimeChange.vue <template><el-date-pickerv-model"…

SinoDB备份恢复工具之onbar

onbar是SinoDB数据库的备份工具之一&#xff0c;它可以根据用户选择的线程数量并行地运行备份或恢复。不同于 ontape&#xff0c;onbar 必须先安装和配置存储管理器&#xff0c;进行才能备份和恢复。 1. onbar功能特性 支持选择具体的存储空间进行备份或恢复 支持基于时间点的…

Codeforces Round #818 (Div. 2) A-C

人类智慧 A. 题意&#xff1a;求满足1<a,b<n且lcm(a,b)/gcd(a,b)<3的(a,b)的个数 转化 a/gcd*b*gcd<3 可以划归为1*2 1*1 2*1 3*1 1*3 则可以转变成一个统计倍数问题 #include<bits/stdc.h> using namespace std; using ll long long; using pii pair&…

【总结】在嵌入式设备上可以离线运行的LLM--Llama

文章目录 Llama 简介运用另一种&#xff1a;MLC-LLM 一个令人沮丧的结论在资源受限的嵌入式设备上无法运行LLM&#xff08;大语言模型&#xff09;。 一丝曙光&#xff1a;tinyLlama-1.1b&#xff08;10亿参数&#xff0c;需要至少2.98GB的RAM&#xff09; Llama 简介 LLaMA…

【与C++的邂逅】---- 函数重载与引用

关注小庄 顿顿解馋(▿) 喜欢的小伙伴可以多多支持小庄的文章哦 &#x1f4d2; 数据结构 &#x1f4d2; C 引言 : 上一篇博客我们了解了C入门语法的一部分&#xff0c;今天我们来了解函数重载&#xff0c;引用的技术&#xff0c;请放心食用 ~ 文章目录 一. &#x1f3e0; 函数重…

OSPF之单区域配置

文章目录 单区域配置项目背景项目分析拓扑图配置思路基础配置命令查看路由器接口IP地址信息OSPF配置 测试PC1与PC2互通查看OSPF邻居表修改OSPF路由器的router-id完美的OSPF配置命令写法常用查询命令 单区域配置 项目背景 企业内部存在多个部门&#xff0c;分别属于不同的网段…

MyBatis-Plus04(条件构造器)

条件构造器和常用接口 wrapper介绍 Wrapper &#xff1a; 条件构造抽象类&#xff0c;最顶端父类 AbstractWrapper &#xff1a; 用于查询条件封装&#xff0c;生成 sql 的 where 条件 QueryWrapper &#xff1a; 查询条件封装 UpdateWrapper &#xff1a; Update 条件封装 A…