当前位置: 首页 > news >正文

【优先级队列 之 堆的实现】

文章目录

  • 前言
  • 优先级队列 PriorityQueue
    • 优先队列的模拟实现
    • 堆的储存方式
    • 堆的创建
    • 建堆的时间复杂度
    • 堆的插入与删除
  • 总结


前言


优先级队列 PriorityQueue

概念:对列是先进先出的的数据结构,但有些情况,数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。所以像这种情况用队列不太合适:在手机上玩游戏时,如果有来电,系统应该优先处理打进来的电话。以前是来电显示充满整个画面,现在变成了一个小窗。

优先队列的模拟实现

PriorityQueue的底层使用了堆这种数据结构(PriorityQueue底层实现是一个完全二叉树,完全二叉树又分为大根堆和小根堆)

概念:
小根堆:根节点比左右孩子都小。只考虑根和左右节点的关系,不考虑左右节点的哪个大。
大根堆:根节点比左右孩子都大

堆的储存方式

在这里插入图片描述
将元素存储到数组中后,可以根据二叉树章节的性质5对树进行还原。假设为节点在数组中的下标,则有: 如果为0,则表示的节点为根节点,否则节点的双亲节点为(i 1)/2
●如果2i+ 1小于节点个数,则节点的左孩子下标为2 门中1,否则没有左孩了
●如果2
i+2小于节点个数,则节点的右孩子下标为2
1+ 2,否则没有右孩子

堆的创建

  1. 让parent标记需要调整的节点,child标记parent的左孩子(注意: parent如果有孩子一 定先是有左孩子)
  2. 如果parent的左孩子存在,即:child < size,进行以下操作, 直到parent的左孩子不存在
    parent右孩子是否存在,存在找到左右孩子中最大的孩子,让child进行标记
  3. 将parent 与较大的孩子child比较,如果:
    parent小于较大的孩子child,交换parent与较大的孩子child,交换完成之后,parent中小的元素向下移动,并继续向下调整,即parent = child; child = parent*2+1;然后继续
    否则:退出循环。
public class TestHeap {//创建一个数组public int[] elem;public int useSize;//有效元素//构造方法给elem分配内存public TestHeap() {this.elem = new int[10];}//初始化elem数组,给elem传入元素public void initElem(int[] array){for (int i = 0; i < array.length; i++) {elem[i] = array[i];useSize++;}}/*** 创建大根堆的代码*/public void createHeap(){for (int parent =(useSize-1-1)/2 ; parent >=0 ; parent--) {siftDown(parent,useSize);}}/*** 向下调整* @param parent* @param len*///让child标记根的左孩子,如果左孩子大于数组长度则进行下面操作// 如果右孩子小于长度并且左孩子的值小于右孩子的值,让左孩子移到右孩子上private void siftDown(int parent,int len){int child = 2*parent+1;while(child < len){if (child+1 < len && elem[child] < elem[child+1]){child = child+1;}//此时child保存的是孩子节点中最大的值//如果左孩子大于根节点,两者的值交换。if (elem[child] > elem[parent]) {//和根节点交换int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;//交换完再换位置parent = child;//根节点移到孩子节点上child = 2*parent+1;//孩子节点再往下移}else{break;}}}
}public class Test {public static void main(String[] args) {TestHeap testHeap = new TestHeap();int[] array={27,15,19,18,28,34,65,49,25,37};testHeap.initElem(array);testHeap.createHeap();System.out.println("========");}
}

建堆的时间复杂度

在这里插入图片描述
因此:建堆的时间复杂度是0(N)

堆的插入与删除

堆的插入:
在这里插入图片描述

    private void swap(int i,int j){int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}//向上调整public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,elem.length*2);}elem[usedSize] = val;siftUp(usedSize);usedSize++;}public boolean isFull(){return usedSize == elem.length;}public void siftUp(int child){int parent = (child-1)/2;while(child > 0){if (elem[child] > parent){swap(child,parent);child = parent;parent = (child-1)/2;}else{break;}}}

堆的删除
注意:这里的删除指的是删除堆顶的元素

  1. 将0下标的的堆顶元素和堆的最后一个元素交换
  2. 将堆的有效个数usedSize–
  3. 对堆进行向下调整
    //删除堆顶元素public int pop(){if (empty()){return -1;}int oldVal = elem[0];swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);return oldVal;}public boolean empty(){return usedSize == 0;}

总结

本章节学习如何实现一个堆,如何运用到向上调整,向下调整。

相关文章:

【优先级队列 之 堆的实现】

文章目录 前言优先级队列 PriorityQueue优先队列的模拟实现 堆堆的储存方式堆的创建建堆的时间复杂度堆的插入与删除 总结 前言 优先级队列 PriorityQueue 概念&#xff1a;对列是先进先出的的数据结构&#xff0c;但有些情况&#xff0c;数据可能带有优先级&#xff0c;一般出…...

Vue中$watch()方法和watch属性的区别

vue中$watch()和watch属性都是监听值的变化的&#xff0c;是同一个作用&#xff0c;但是有两个不同写法。 用法一&#xff1a; //注意&#xff1a;这种方法是监听不到对象的变化的。 this.$watch((newVal,oldVal)>{ }) 用法二&#xff1a; watch:{xxx:(newVal,oldVal)>…...

openssl3.2 - 官方demo学习 - test - certs - 001 - Primary root: root-cert

文章目录 openssl3.2 - 官方demo学习 - test - certs - 001 - Primary root: root-cert概述笔记备注END openssl3.2 - 官方demo学习 - test - certs - 001 - Primary root: root-cert 概述 实验前置条件为 openssl3.2 - linux脚本(.sh)调用openssl命令行参数的简单确认方法 …...

小程序商城能不能自己开发?

在数字化时代&#xff0c;小程序商城已经成为商家拓展销售渠道、提升品牌影响力的重要工具。那么&#xff0c;商家能否自己动手开发小程序商城呢&#xff1f;答案是肯定的。接下来&#xff0c;以乔拓云为例&#xff0c;为大家详细介绍如何自己搭建小程序商城。 首先&#xff0c…...

GPTBots:利用FlowBot中的卡片和表单信息,提供丰富的客服体验

在当今的数字化时代&#xff0c;客户服务的形式和体验正在经历着前所未有的变革。传统的文字消息方式已经无法满足现代用户对于服务体验的多元化需求。那么&#xff0c;如何才能在这个信息爆炸的时代&#xff0c;让我们的服务方式更加个性化、多样化&#xff0c;从而提供更丰富…...

ERC20 解读

1.ERC20 什么叫做代币&#xff1f; 代币可以在以太坊中表示任何东西&#xff1a; 在线平台中的信誉积分游戏中一个角色的技能彩票卷金融资产类似于公司股份的资产像美元一样的法定货币一盎司黄金及更多... 以太坊的这种强大特点必须以强有力的标准来处理&#xff0c;对吗&a…...

C#,入门教程(31)——预处理指令的基础知识与使用方法

上一篇&#xff1a; C#&#xff0c;入门教程(30)——扎好程序的笼子&#xff0c;错误处理 try catchhttps://blog.csdn.net/beijinghorn/article/details/124182386 Visual Studio、C#编译器以及C#语法所支持的预处理指令&#xff0c;绝对是天才设计。 编译程序的时候会发现&am…...

Java SE:面向对象(下)

1. static关键字 静态区的特点&#xff1a;静态区里面的每一样东西都是唯一有且仅有一个的&#xff0c;如此时str1 "abc"即此时静态区里面已经创建了字符串abc并将abc地址赋给str1&#xff0c;后面在进行赋值也不会在静态区开辟一串新的"abc" 1.1 static修…...

搭建开源数据库中间件MyCat2-配置mysql数据库双主双从

mycat2官网&#xff1a;MyCat2 前言&#xff1a;mycat2下载地址无法访问&#xff0c;不知道是不是被DNS污染了&#xff0c;还是需要搭梯子访问&#xff0c;所以我只能找到1.21的版本进行安装。搭建mycat2的前提是搭建数据库主从复制。 架构&#xff1a;双主双从 配置&#xf…...

Oracle 19c rac集群管理 -------- 集群启停操作过程

Oracle rac集群启停操作过程 首先查看数据库的集群的db_unique_name SQL> show parameter nameNAME TYPE VALUE ------------------------------------ ----------- --------------------------- cdb_cluster_name …...

【Java】HttpServlet类中前后端交互三种方式(query string、form表单、JSON字符串)

在前后端的交互中&#xff0c;前端通过以下三种方式来与后端进行交互&#x1f31f; ✅query string ✅form表单 ✅JSON字符串 下面我们将书写这三种方式的后端代码并进行讲解 1、Query String QueryString即在url中写入键值对&#xff0c;一般用doGet方法进行交互 代码如下 …...

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记

0. Outline 1. Graph Search Basis Configuration Space等概念 机器人配置: 指机器人位置和所有点的表示。 DOF: 指用于表示机器人配置所需的最小的实数坐标的数量n。 C-space: 包含机器人n维所有配置的空间。 在C-space中机器人的pose是一个点。 机器人在C-space中被表示为一…...

安装向量数据库milvus可视化工具attu

使用docker安装的命令和简单就一个命令&#xff1a; docker run -p 8000:3000 -e MILVUS_URL{milvus server IP}:19530 zilliz/attu:v2.3.5sunyuhuasunyuhua-HKF-WXX:~/dockercom/milvus$ docker run -p 8000:3000 -e MILVUS_URL127.0.0.1:19530 zilliz/attu:latest yarn run…...

STM32标准库开发——串口发送/单字节接收

USART基本结构 串口发送信息 启动串口一的时钟 RCC_APB2PeriphClockCmd(RCC_APB2Periph_USART1,ENABLE);初始化对应串口一的时钟&#xff0c;引脚&#xff0c;将TX引脚设置为复用推挽输出。 RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA,ENABLE); GPIO_InitTypeDef GPIO_In…...

jdk17新特性——文本块(即多行的字符串)增强

目录 一、文本块(即多行的字符串)概述二、文本块(即多行的字符串)示例2.1、jdk17之前 多行字符串处理方式2.2、jdk17及以后版本 多行字符串处理方式2.3、注意事项 三、文本块(即多行的字符串)转义字符示例3.1、jdk17及以后版本 多行字符串的转义字符处理方式示例一3.2、jdk17及…...

阿里云ECS使用docker搭建mysql服务

目录 1.确保正确安装好docker 2.安装mysql镜像 3.创建容器&#xff08;设置端口映射、目录映射&#xff09; 1.确保正确安装好docker 安装教程&#xff1a; 阿里云ECS(CentOS镜像)安装docker-CSDN博客https://blog.csdn.net/qq_62262918/article/details/135686614?spm10…...

Windows给docker设置阿里源

windows环境搭建专栏&#x1f517;点击跳转 Windows系统的docker设置阿里源 文章目录 Windows系统的docker设置阿里源1.获得镜像加速器2.配置docker 由于我们生活在中国大陆&#xff0c;所以外网的访问总是那么慢又困难&#xff0c;用docker拉取几兆的小镜象还能忍受&#xff…...

安裝火狐和穀歌流覽器插件FoxyProxy管理海外動態IP代理

代理生態系統擁有大量有用的實用程式&#xff0c;使海外代理IP代理設置的使用變得簡單起來。其中一種類型叫做代理管理工具&#xff0c;像FoxyProxy就是該工具集比較受歡迎的。 本文將全面解析FoxyProxy擴展的功能和特性、Foxyproxy怎麼下載、以及如何在穀歌流覽器和火狐流覽器…...

C++重新入门-函数重载

1.函数重载的定义 C函数重载&#xff08;Function Overloading&#xff09;是指在同一作用域内&#xff0c;可以定义多个函数&#xff0c;它们具有相同的名称但参数列表不同的特性。通过函数重载&#xff0c;可以使用相同的函数名来实现不同的操作&#xff0c;提高了代码的可读…...

niushop靶场漏洞查找-文件上传漏洞等(超详细)

实战漏洞-niushop 一.端口扫描 http://www.xxx.com/index.php?s/admin/login 这里查询到后面的url有且仅有一个&#xff0c;目测估计是后台 访问url 发现确实是后台 二、找漏洞 Sql注入漏洞1&#xff1a; 点击进去 修改id www.xxx.com/index.php?s/goods/goodslist&…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...