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

(优先级队列(堆)) 【本节目标】 1. 掌握堆的概念及实现 2. 掌握 PriorityQueue 的使用

优先级队列(堆)

  • 1. 优先级队列
    • 1.1 概念
  • 2. 优先级队列的模拟实现
    • 2.1 堆的概念
    • 2.2 堆的存储方式
    • 2.3 堆的创建
      • 2.3.1 堆向下调整
      • 2.3.2 堆的创建
      • 2.3.3 建堆的时间复杂度

【本节目标】

  1. 掌握堆的概念及实现
  2. 掌握 PriorityQueue 的使用

1. 优先级队列

1.1 概念

前面介绍过队列,队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列,该中场景下,使用队列显然不合适,比如:在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话;初中那会班主任排座位时可能会让成绩好的同学先挑座位。
在这种情况下,数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)

2. 优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构,而堆实际就是在完全二叉树的基础上进行了一些调整。

2.1 堆的概念

如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。
    在这里插入图片描述

2.2 堆的存储方式

从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储
在这里插入图片描述
注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率比较低
在这里插入图片描述
将元素存储到数组中后,可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标,则有:

  • 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
  • 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
  • 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子

2.3 堆的创建

2.3.1 堆向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据,如果将其创建成堆呢?
在这里插入图片描述
仔细观察上图后发现:根节点的左右子树已经完全满足堆的性质,因此只需将根节点向下调整好即可
向下过程(以小堆为例)

  1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
  2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在
  • parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标
  • 将parent与较小的孩子child比较,如果:
    • parent小于较小的孩子child,调整结束
    • 否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子树不满足对的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。
      在这里插入图片描述

大根堆:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
小根堆代码:

public void shiftDown(int[] array, int parent) {// child先标记parent的左孩子,因为parent可能右左没有右int child = 2 * parent + 1;int size = array.length;while (child < size) {// 如果右孩子存在,找到左右孩子中较小的孩子,用child进行标记if(child+1 < size && array[child+1] < array[child]){child += 1;}// 如果双亲比其最小的孩子还小,说明该结构已经满足堆的特性了if (array[parent] <= array[child]) {break;}else{// 将双亲与较小的孩子交换int t = array[parent];array[parent] = array[child];array[child] = t;// parent中大的元素往下移动,可能会造成子树不满足堆的性质,因此需要继续向下调整parent = child;child = parent * 2 + 1;}}
}

注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
时间复杂度分析

最坏的情况即图示的情况,从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(log2 n)

2.3.2 堆的创建

那对于普通的序列{ 1,5,3,8,7,6 },即根节点的左右子树不满足堆的特性,又该如何调整呢?
在这里插入图片描述
参考代码:

public static void createHeap(int[] array) {// 找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整int root = ((array.length-2)>>1);for (; root >= 0; root--) {shiftDown(array, root);}
}

2.3.3 建堆的时间复杂度

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):
在这里插入图片描述
在这里插入图片描述
因此:当我们采用向下调整去建堆的时候,建堆的时间复杂度为O(N)。

相关文章:

(优先级队列(堆)) 【本节目标】 1. 掌握堆的概念及实现 2. 掌握 PriorityQueue 的使用

优先级队列&#xff08;堆&#xff09; 1. 优先级队列1.1 概念 2. 优先级队列的模拟实现2.1 堆的概念2.2 堆的存储方式2.3 堆的创建2.3.1 堆向下调整2.3.2 堆的创建2.3.3 建堆的时间复杂度 【本节目标】 掌握堆的概念及实现掌握 PriorityQueue 的使用 1. 优先级队列 1.1 概念…...

优化数据库结构

MySQL学习大纲 一个好的数据库设计方案对于数据库的性能尝尝会起到事倍功半的效果&#xff0c;合理的数据库结构不仅使数据库占用更小的磁盘空间&#xff0c;而且使查询速度更快。数据库结构的设计需要考虑数据冗余、查询和更新速度、字段的数据类型是否合理等多方面的内容&…...

密云生活的初体验

【】在《岁末随笔之碎碎念》里&#xff0c;我通告了自己搬新家的事情。乙巳年开始&#xff0c;我慢慢与大家分享自己买房装修以及在新家的居住体验等情况。 跳过买房装修的内容&#xff0c;今天先说说这三个月的生活体验。 【白河】 潮白河是海河水系五大河之一&#xff0c;贯穿…...

图像分类与目标检测算法

在计算机视觉领域&#xff0c;图像分类与目标检测是两项至关重要的技术。它们通过对图像进行深入解析和理解&#xff0c;为各种应用场景提供了强大的支持。本文将详细介绍这两项技术的算法原理、技术进展以及当前的落地应用。 一、图像分类算法 图像分类是指将输入的图像划分为…...

计算机网络——流量控制

流量控制的基本方法是确保发送方不会以超过接收方处理能力的速度发送数据包。 通常的做法是接收方会向发送方提供某种反馈&#xff0c;如&#xff1a; &#xff08;1&#xff09;停止&等待 在任何时候只有一个数据包在传输&#xff0c;发送方发送一个数据包&#xff0c;…...

体验 DeepSeek 多模态大模型 Janus-Pro-7B

含有图片的链接&#xff1a; https://mp.weixin.qq.com/s/i6kuVcGU1CUMYRPDM-bKog?token2020918682&langzh_CN 继上篇文章下载了 Janus-Pro-7B 后&#xff0c;准备本地运行时发现由于电脑配置配置太低&#xff08;显存小于24G&#xff09;&#xff0c;无法运行&#xff0…...

使用mockttp库模拟HTTP服务器和客户端进行单元测试

简介 mockttp 是一个用于在 Node.js 中模拟 HTTP 服务器和客户端的库。它可以帮助我们进行单元测试和集成测试&#xff0c;而不需要实际发送 HTTP 请求。 安装 npm install mockttp types/mockttp模拟http服务测试 首先导入并创建一个本地服务器实例 import { getLocal } …...

解决每次打开终端都需要source ~/.bashrc的问题(记录)

新服务器或者电脑通常需要设置一些环境变量&#xff0c;例如新电脑安装了Anaconda等软件&#xff0c;在配置环境变量后发现每次都需要重新source&#xff0c;非常麻烦&#xff0c;执行下面添加脚本实现一劳永逸 vim .bash_profile# .bash_profileif [ -f ~/.bashrc ]; then. ~…...

UE5 蓝图学习计划 - Day 14:搭建基础游戏场景

在上一节中&#xff0c;我们 确定了游戏类型&#xff0c;并完成了 项目搭建、角色蓝图的基础设置&#xff08;移动&#xff09;。今天&#xff0c;我们将进一步完善 游戏场景&#xff0c;搭建 地形、墙壁、机关、触发器 等基础元素&#xff0c;并添加角色跳跃功能&#xff0c;为…...

C++常用拷贝和替换算法

算法简介&#xff1a; copy // 容器内指定的元素拷贝到另一容器replace // 将容器内指定范围的旧元素改为新元素replace_if // 容器内指定范围满足条件的元素替换为新元素swap //互换两个容器的元素 1. copy 功能描述&#xff1a; 将容器内指定范围的数据拷贝到另一容器中函…...

取消和确认按钮没有显示的问题

取消和确认按钮没有显示的问题<template #footer> <template #footer> <!-- 使用插槽名称 #footer --> <span class"dialog-footer"> <el-button click"dialogVisible false">取消</el-button> …...

Python安居客二手小区数据爬取(2025年)

目录 2025年安居客二手小区数据爬取观察目标网页观察详情页数据准备工作&#xff1a;安装装备就像打游戏代码详解&#xff1a;每行代码都是你的小兵完整代码大放送爬取结果 2025年安居客二手小区数据爬取 这段时间需要爬取安居客二手小区数据&#xff0c;看了一下相关教程基本…...

Java/Kotlin HashMap 等集合引发 ConcurrentModificationException

在对一些非并发集合同时进行读写的时候&#xff0c;会抛出 ConcurrentModificationException 异常产生示例 示例一&#xff08;单线程&#xff09;&#xff1a; 遍历集合时候去修改 抛出 ConcurrentModificationException 的主要原因是当你在遍历一个集合&#xff08;如 Map…...

【Day31 LeetCode】动态规划DP Ⅳ

一、动态规划DP Ⅳ 1、最后一块石头的重量II 1049 这题有点像脑筋急转弯&#xff0c;尽量让石头分成重量相同的两堆&#xff08;尽可能相同&#xff09;&#xff0c;相撞之后剩下的石头就是最小的。明白这一点&#xff0c;就与上一篇博客里的划分等和数组很相似。划分等和数组…...

Unity 2D实战小游戏开发跳跳鸟 - 记录显示最高分

上一篇文章中我们实现了游戏的开始界面,在开始界面中有一个最高分数的UI,本文将接着实现记录最高分数以及在开始界面中显示最高分数的功能。 添加跳跳鸟死亡事件 要记录最高分,则需要在跳跳鸟死亡时去进行判断当前的分数是否是最高分,如果是最高分则进行记录,如果低于之前…...

Ollama AI 开发助手完全指南:从入门到实践

本文将详细介绍如何使用 Ollama AI 开发助手来提升开发效率,包括环境搭建、模型选择、最佳实践等全方位内容。 © ivwdcwso (ID: u012172506) 目录 基础环境配置模型选择与使用开发工具集成实践应用场景性能优化与注意事项最佳实践总结一、基础环境配置 1.1 系统要求 在…...

Racecar Gym

Racecar Gym 参考&#xff1a;https://github.com/axelbr/racecar_gym/blob/master/README.md 1. 项目介绍 Racecar Gym 是一个基于 PyBullet 物理引擎的 reinforcement learning (RL) 训练环境&#xff0c;模拟微型 F1Tenth 竞速赛车。它兼容 Gym API 和 PettingZoo API&am…...

代码随想录36 动态规划

leetcode 343.整数拆分 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。 示例 2: 输入: n 1…...

离散时间傅里叶变换(DTFT)公式详解:周期性与连续性剖析

摘要 离散时间傅里叶变换&#xff08;DTFT&#xff09;是数字信号处理领域的重要工具&#xff0c;它能将离散时间信号从时域转换到频域&#xff0c;揭示信号的频率特性。本文将深入解读DTFT公式&#xff0c;详细阐述其具有周期性和连续性的原因&#xff0c;帮助读者全面理解DT…...

深度学习|表示学习|卷积神经网络|Batch Normalization在干什么?|19

如是我闻&#xff1a; Batch Normalization&#xff08;批归一化&#xff0c;简称 BN&#xff09; 是 2015 年由 Ioffe 和 Szegedy 提出 的一种加速深度神经网络训练并提高稳定性的技术。 它的核心思想是&#xff1a;在每一层的输入进行归一化&#xff0c;使其均值接近 0&…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...