【用Java学习数据结构系列】用堆实现优先级队列

看到这句话的时候证明：此刻你我都在努力

加油陌生人

个人主页：Gu Gu Study
专栏：用Java学习数据结构系列
喜欢的一句话： 常常会回顾努力的自己，所以要为自己的努力留下足迹

喜欢的话可以点个赞谢谢了。
作者：小闭

优先级队列（Priority Queue）

优先级队列是一种抽象数据类型（ADT），它存储一组元素，每个元素都有一个与之关联的优先级。在优先级队列中，元素的访问顺序取决于它们的优先级，而不是它们被插入的顺序。优先级最高的元素总是最先被移除。

优先级队列的关键特性包括：

  1. 优先级规则：元素根据其优先级进行排序。通常有两种优先级规则：
    • 最大优先级：最高优先级的元素（数值最大）最先被移除。
    • 最小优先级：最高优先级的元素（数值最小）最先被移除。
  1. 插入操作：允许将新元素添加到队列中，并根据其优先级放置在正确的位置。
  2. 删除操作：移除当前优先级最高的元素。这通常被称为“弹出”（pop）操作。
  3. 查找操作：有时优先级队列支持查找当前优先级最高的元素，这被称为“查看”（peek）或“顶部”（top）操作。
  4. 动态性：优先级队列能够动态地插入和删除元素，而不仅仅是静态地存储数据。

优先级队列的常见应用：

  • 任务调度：在操作系统中，优先级队列用于管理进程或线程的调度，其中每个任务都有一个优先级。
  • 事件驱动模拟：在模拟中，事件根据其发生的时间点（优先级）被处理。
  • 图算法：在图算法如迪杰斯特拉（Dijkstra）算法和普里姆（Prim）算法中，优先级队列用于选择下一个要处理的顶点或边。
  • 数据压缩：例如霍夫曼编码，使用优先级队列来构建最优前缀编码。
  • 网络流问题：在解决最大流问题时，优先级队列用于快速找到增广路径。

实现优先级队列的数据结构：

  • 数组：简单但效率不高，因为插入和删除操作可能需要移动大量元素。
  • 链表：可以快速插入和删除，但查找特定元素可能较慢。
  • 二叉堆：最常用的实现方式，特别是二叉最小堆和二叉最大堆，它们提供了对数时间复杂度的插入和删除操作。
  • 平衡二叉搜索树：如AVL树或红黑树，提供了对数时间的插入、删除和查找操作。
  • 斐波那契堆：在某些操作（如删除最小元素）上非常高效，但插入和合并操作可能较慢。

优先级队列是一种非常有用的数据结构，它在需要根据元素的相对重要性进行操作的场景中非常有用。

但今天我们学习的是用二叉堆来实现优先级队列，主要了解其中的原理。

堆（Heap）

数据结构中的“堆”（Heap）是一种特殊的完全二叉树，它满足以下性质：

  1. 堆序性：在最大堆中，每个节点的值都不小于其子节点的值；在最小堆中，每个节点的值都不大于其子节点的值。
  2. 完全二叉树：除了最后一层外，每一层都被完全填满，并且最后一层的所有节点都尽可能地向左排列。

堆通常用于实现优先队列，它支持以下操作：

  • 插入（Insert）：在堆的末尾添加一个新元素，然后通过上浮（Percolate Up）操作来恢复堆的性质。
  • 删除最大/最小元素（Extract Max/Min）：移除最大（在最大堆中）或最小（在最小堆中）的元素，通常这个元素是堆的根节点。然后，将最后一个元素移动到根位置，并进行下沉（Percolate Down）操作来恢复堆的性质。
  • 查找最大/最小元素（Get Max/Min）：在最大堆中返回根节点的值，在最小堆中也是返回根节点的值。
  • 堆排序（Heap Sort）：通过构建一个最大堆，然后反复移除堆顶元素并重建堆，可以实现数组的原地排序。

堆可以用数组来实现，其中数组的索引与树中的位置有直接的对应关系。对于数组中的任意元素，其父节点和子节点的索引可以通过以下公式计算：

  • 父节点索引：(i-1)/2（其中i是当前节点的索引）
  • 左子节点索引：2*i + 1
  • 右子节点索引：2*i + 2

堆的实现通常需要对数组进行操作，以确保在进行插入和删除操作时，能够快速地维护堆的性质。堆是一种非常高效的数据结构，特别是在需要频繁插入和删除最大或最小元素的场景中。

堆的两种储存方式

我们上面说过堆的堆序性，以及堆其实是一颗完全二叉树。那么下面就展示了堆的两种储存方式。大根堆和小根堆 。我们先看下图。

为什么使用完全二叉树呢？因为其实堆的储存结构是一个线性数组，如果使用非完全二叉树则就会比较浪费空间。

小根堆：其根节永远小于他的两个左右孩子。

大根堆：其根节永远大于他的两个左右孩子。

了解完了堆的储存方式后，我们就该模拟实现一下，来加深一下对堆的理解。

堆的模拟实现

首先要模拟堆的实现我们就要了解一下堆的调整方式。

堆有向上调整和向下调整。

那么我们怎么了解这两个调整呢？

顾名思义，向下调整就是在给定节点处往下调整，使这个节点往下形成的子树成为一个堆（大根堆或小根堆）

堆的向下调整

向下调整从给点的节点，不断往下调整，我这里假设是调整为小根堆。那么调整的过程就是看两个孩子节点是否比父节点小，如果小就交换一下两个节点的值就可以了。这里调整结束的条件就是child大于树的节点的个数，所以while的条件为（child<=len）。

代码实现）（小根堆为例）：

public static void shiftDown(int[] array, int parent,int len) {int child=2*parent+1;  //父节点的左孩子while(child<=len){if(child+1<=len&&array[child+1]<array[child]){child=child+1;}if(array[child]<array[parent]){swap(array,child,parent);}parent=child;child=2*child+1;}}private static void swap(int[] array, int child, int parent) {int tmp=array[child];array[child]=array[parent];array[parent]=tmp;}

使用向下调整建成小根堆

使用向下调整创建小根堆的步骤主要就是，找最后一个节点的父节点(即：(a.length-1-1)/2)开始，不断往前，每一个节点都进行一个向下调整，调整完毕后，就可以创建成一个小根堆了。如果要创建大根堆只需要改一下向下调整的比较部分即可。

import java.util.Arrays;public class T {public static void main(String[] args) {int[] a={273,34,67,22,11,66,8,3};for (int i = (a.length-1-1)/2; i >=0 ; i--) {shiftDown(a,i,a.length-1);}System.out.println(Arrays.toString(a));}public static void shiftDown(int[] array, int parent,int len) {int child=2*parent+1;  //父节点的左孩子while(child<=len){if(child+1<=len&&array[child+1]<array[child]){child=child+1;}if(array[child]<array[parent]){swap(array,child,parent);}parent=child;child=2*child+1;}}private static void swap(int[] array, int child, int parent) {int tmp=array[child];array[child]=array[parent];array[parent]=tmp;}}

注意：堆的向下调整主要是运用在建堆，即：给定你一个数组，直接将这个数组创建成大根堆或小根堆。

想要一个一个插入的话，我们是要用到向上调整的。

堆的向上调整

堆的向上调整与向下调整相似，只是调整方向是不断往上的，所以在我们插入数据时（通常是尾插）那么我们就得使用向上调整了，因为这样我们只需要调整这个节点就好了。如果我们向下调整的话，还是需要将每个节点进行调整。

代码实现（小根堆为例）：

private static void swap(int[] array, int child, int parent) {int tmp=array[child];array[child]=array[parent];array[parent]=tmp;}public static void shiftUp(int[] array, int child) {int parent=(child-1)/2;while(child>0){if(array[child]<array[parent]){swap(array,child,parent);child=parent;parent=(child-1)/2;}else {break;}}
}

使用向上调整一个一个插入创建小根堆

我们随机生成一个随机数，在加入数组，然后在进行调整即可。这样就是逐一插入实现小根堆，大根堆同理。

private static void swap(int[] array, int child, int parent) {int tmp=array[child];array[child]=array[parent];array[parent]=tmp;}public static void shiftUp(int[] array, int child) {int parent=(child-1)/2;while(child>0){if(array[child]<array[parent]){swap(array,child,parent);child=parent;parent=(child-1)/2;}else {break;}}
}public static void main(String[] args) {int[] arr=new int[10];Random random=new Random();for (int i = 0; i < 10; i++) {int n= random.nextInt(100);arr[i]=n;shiftUp(arr,i);}System.out.println(Arrays.toString(arr));
}

检验一下结果，确实是一个小根堆。

向下调整和向上调整的总结

向下调整：适用于给定一个数组，要将数组中的元素建成堆的形式，这时我们用向下调整的话是比较合适的，相比与向上调整是比较快的从时间复杂度上看。

向上调整：适用于要将数据一个一个插入，使其每次插入完成后还是堆的形式，这时因为数据通常是插入在数组尾端然后在进行调整。所以只需要调用向上调整一下为节点就可以，而这是向下调整做不到的。

模拟实现优先级队列的方法接口

如下：简单实现了offer，poll，peek方法。

offer：将数据进行尾插后，直接对该节点进行向下调整。

poll：我们将头节点数据，用另一个变量进行储存后，与最后一个节点进行调换位置然后进行一次i向下调整。

peek：查看根节点的数据。

注意：我们这里吧数组当作一颗完全二叉树，即数组的下标相当于层序遍历的顺序对应的那个节点。


public void offer(int e) {array[size++] = e;shiftUp(array,size - 1);}public int poll() {int oldValue = array[0];array[0] = array[--size];shiftDown(array,0,size-1);return oldValue;}public int peek() {return array[0];}

以下是全部代码：

public class MyPriorityQueue {private int[] array = new int[100];private int size = 0;public  void shiftDown(int[] array, int parent, int len) {int child = 2 * parent + 1;  //父节点的左孩子while (child <= len) {if (child + 1 <= len && array[child + 1] < array[child]) {child = child + 1;}if (array[child] < array[parent]) {swap( child, parent);}parent = child;child = 2 * child + 1;}}private  void swap( int child, int parent) {int tmp = array[child];array[child] = array[parent];array[parent] = tmp;}public  void shiftUp(int[] array, int child) {int parent = (child - 1) / 2;while (child > 0) {if (array[child] < array[parent]) {swap(child, parent);child = parent;parent = (child - 1) / 2;} else {break;}}}public void offer(int e) {array[size++] = e;shiftUp(array,size - 1);}public int poll() {int oldValue = array[0];array[0] = array[--size];shiftDown(array,0,size-1);return oldValue;}public int peek() {return array[0];}public static void main(String[] args) {MyPriorityQueue queue=new MyPriorityQueue();queue.offer(1);queue.offer(4);queue.offer(33);queue.offer(9);queue.offer(14);queue.offer(6);for (int i = 0; i < queue.size; i++) {System.out.print(queue.array[i]+" ");}System.out.println();queue.poll();for (int i = 0; i < queue.size; i++) {System.out.print(queue.array[i]+" ");}}}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

RK3562/3588系列之6—yolov5模型的部署

RK3562/3588系列之6—yolov5模型的部署

RK3562/3588系列之6—yolov5模型的部署 1.yolov5模型训练2.训练好的模型转成onnx格式3.模型从onnx格式转RKNN3.1 onnx2rknn.py3.2 onnx2rknn.py3.3 直接使用rknn.api3.4 rknn_model_zoo中的转换代码3.5 LubanCat-RK系列板卡官方资料4.RK NPU c++推理4.1交叉编译4.2 开发板执行编…
阅读更多...
整数在内存中的存储原码反码补码

整数在内存中的存储原码反码补码

目录 1.整数在内存中以二进制的形式存在 1.1&#xff08;正数存储情况&#xff09; 1.2 负数存储情况 1.3整数的补码如何得到原码 2.无符号整数的原反补码 小心&#xff01;VS2022不可直接接触&#xff0c;否则&#xff01;没这个必要&#xff0c;方源面色淡然一把抓住&am…
阅读更多...
ChatGPT提示词-中文版(awesome-chatgpt-prompts中文版)

ChatGPT提示词-中文版(awesome-chatgpt-prompts中文版)

原是Github上110.6K星的项目&#xff1a;GitHub - f/awesome-chatgpt-prompts: This repo includes ChatGPT prompt curation to use ChatGPT better. 我翻译成了中文需要自提 我用夸克网盘分享了「Chat GPT提示词.csv」&#xff0c;点击链接即可保存。打开「夸克APP」在线查看…
阅读更多...
为解决bypy大文件上传报错—获取百度云文件直链并使用Aria2上传文件至服务器

为解决bypy大文件上传报错—获取百度云文件直链并使用Aria2上传文件至服务器

问题描述 一方面组内的服务器的带宽比较小&#xff0c;另一方面使用bypy方式进行大文件(大于15G)上传时会报错&#xff08;虽然有时可以成功上传&#xff0c;但是不稳定&#xff09;&#xff1a; 解决方式 总体思路: 获得云盘需要下载文件的直链复制直链到服务器中使用自带…
阅读更多...
CRM如何助力科技服务机构突破业务瓶颈？

CRM如何助力科技服务机构突破业务瓶颈？

在当今知识经济时代&#xff0c;科技服务机构面临着复杂的业务环境和多样化的客户需求。客户管理系统&#xff08;CRM&#xff09;在这个领域的应用正逐渐成为机构提升运营效率、优化客户服务的关键。 科技服务行业的业务特点 知识产权代理行业具有高度的专业性和复杂性。其业…
阅读更多...
[记录一个bug]流媒体服务瓶颈排查

[记录一个bug]流媒体服务瓶颈排查

一、抛砖 最近有一个服务器上的rtmp直播服务，搭载了1k路后，无法支撑高码率如6M 8M的视频推流，推流会导致掉帧到个位数。但是看了top和vmstat，没发现明显的瓶颈。程序的单进程多线程，但是在另一台配置更低的服务器上，却没问题。 所以这里干脆记录下瓶颈排查步骤和方法吧。…
阅读更多...
跟《经济学人》学英文：2024年09月14日这期 Demand for high-end cameras is soaring

跟《经济学人》学英文：2024年09月14日这期 Demand for high-end cameras is soaring

Demand for high-end cameras is soaring The ubiquity of smartphones has helped ubiquity: 美 [juːˈbɪkwəti] 到处存在&#xff1b;遍在 注意发音 原文&#xff1a; Buying a Leica feels like buying a piece of art. Made in Germany, the cameras are sold in th…
阅读更多...
《JavaEE进阶》----15.＜Spring Boot 日志＞

《JavaEE进阶》----15.＜Spring Boot 日志＞

本篇文章将记录我学习SpringBoot日志 1.日志文件的用途 2.SpringBoot日志文件的配置 3.用lombook依赖引入Slf4j注解&#xff0c;从而引入log对象。方便我们打印日志。 一、日志的作用 日志主要是为了发现问题、分析问题、定位问题。除此之外、日志还有许多其他的用途。 1.系统监…
阅读更多...
Linux基础---07文件传输（网络和Win文件）

Linux基础---07文件传输（网络和Win文件）

Linux文件传输地图如下&#xff0c;先选取你所需的场景&#xff0c;若你是需要Linux和Linux之间传输文件就查看SCP工具即可。 一.下载网站文件 前提是有网&#xff1a; 检查网络是否畅通命令&#xff1a;ping www.baidu.com&#xff0c;若有持续的返回值就说明网络畅通。Ctr…
阅读更多...
国家网信办就人工智能生成合成内容标识征求意见

国家网信办就人工智能生成合成内容标识征求意见

国家互联网信息办公室发布《人工智能生成合成内容标识办法&#xff08;征求意见稿&#xff09;》&#xff0c;该办法根据《中华人民共和国网络安全法》、《互联网信息服务算法推荐管理规定》、《互联网信息服务深度合成管理规定》、《生成式人工智能服务管理暂行办法》等法律法…
阅读更多...
Neo4j入门案例：西游记

Neo4j入门案例：西游记

创建一个基于《西游记》中“孙悟空”的黑神话版本的知识图谱。这个图谱将会包括《西游记》中的一些主要角色、地点、事件以及它们之间的关系。我们将创建至少10个节点和20个关系&#xff0c;并提供相应的Cypher语句。 数据模型定义 实体类型&#xff08;节点&#xff09; 角色…
阅读更多...
在conda虚拟环境中安装cv2(试错多次总结)

在conda虚拟环境中安装cv2(试错多次总结)

首先保证你创建好了虚拟环境&#xff0c;并在anaconda命令窗口激活虚拟环境 依次输入下列命令&#xff1a; pip install opencv-python3.4.1.15 pip install opencv-contrib-python3.4.1.15 pip install dlib19.6.1 然后测试cv2是否可以使用&#xff0c;输入python 运行pyth…
阅读更多...
RHEL、centOS通过NET模式连接外网的最真实操作经验

RHEL、centOS通过NET模式连接外网的最真实操作经验

切换网络模式 切换至NET模式&#xff08;我这里用的是RHEL7&#xff09; 编辑网卡配置文件 此处我的为/etc/sysconfig/network-scripts/ifcfg-eno16777728 &#xff08;具体可以通过 ls /etc/sysconfig/network-scripts查看到&#xff09; 命令&#xff1a;vim /etc/sysconf…
阅读更多...
【Node.js】初识微服务

【Node.js】初识微服务

概述 Node.js 的微服务架构是一种通过将应用程序分解为独立的、松耦合的小服务的方式进行系统设计。 每个微服务负责处理一个特定的业务功能&#xff0c;并且这些服务可以独立开发、部署、扩展和管理&#xff0c;并且可以通讯。 它的核心思想就是解耦。 微服务和微前端是类…
阅读更多...
火语言RPA流程组件介绍--单选/复选框

火语言RPA流程组件介绍--单选/复选框

&#x1f6a9;【组件功能】&#xff1a;勾选页面单选/复选框元素 配置预览 配置说明 丨目标元素 支持T或# 默认FLOW输入项 通过自动捕获工具捕获(选择元素工具使用方法)或手动填写网页元素的css,xpath&#xff0c;指定对应网页元素作为操作目标 丨操作 对目标元素进行的勾…
阅读更多...
大棚分割数据集，40765对影像，16.9g数据量，0.8米高分二，纯手工标注（arcgis标注）的大规模农业大棚分割数据集。

大棚分割数据集，40765对影像，16.9g数据量，0.8米高分二，纯手工标注（arcgis标注）的大规模农业大棚分割数据集。

数据集名称&#xff1a; &#xff09;“Greenhouse Segmentation Dataset (GSD)” 数据集规模&#xff1a; 包含40,765对用于大棚分割的影像数据&#xff0c;每对影像包括一张原始图像和相应的分割标签图。 数据量&#xff1a; 总数据量约为16.9GB&#xff0c;适合存储在现…
阅读更多...
随想笔记1：CSDN写博客经常崩溃，遇到外链图片转存失败怎么办

随想笔记1：CSDN写博客经常崩溃，遇到外链图片转存失败怎么办

人如果要学习输入&#xff0c;就必定要表达输出&#xff0c;否则无法达成正向良性循环。 所以技术性博客要常写&#xff0c;平台很多&#xff0c;最好是支持markdown的&#xff0c; 1&#xff0c;支持markdown写博客的在线技术类博客网站&#xff1a; CSDN、博客园、稀土掘金…
阅读更多...
搬砖人如何快速找回丢失的数据？盘点4款高效电脑数据恢复工具

搬砖人如何快速找回丢失的数据？盘点4款高效电脑数据恢复工具

各位上班的朋友们&#xff0c;是不是有时候一不小心&#xff0c;就发现自己好不容易存下来的数据找不着了&#xff1f;别慌哈&#xff0c;今天我这个懂点科技的人就来给大家说说几款特别实用的能电脑数据恢复的工具&#xff0c;让你轻轻松松把那些“跑丢了”的数据给找回来&…
阅读更多...
Linux文件系统(上)

Linux文件系统(上)

目录 前言 1.文件接口——用户与文件的“桥梁” 2.C语言中FILE结构与Linux系统调用中fd的关系 3.fd字段如何在文件读写操作中发挥作用 4.fd的分配规则与文件重定向 5.文件缓冲区 6.如何理解Linux中一切皆文件的管理方案 7.涉及代码一览 总结 前言 在Linux中存在“两列”文件…
阅读更多...
Python数据分析 Pandas库-初步认识

Python数据分析 Pandas库-初步认识

Python数据分析 Pandas库-初步认识 认识Pandas ​ pandas是一个非常实用的Python工具&#xff0c;我们可以把它想象成一个超级强大的表格处理工具&#xff0c;它比Excel更智能&#xff0c;操作更为简单。pands可以从各种文件格式&#xff08;CSV、JSON、SQL、Excel&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023