【算法基础实验】排序-最小优先队列MinPQ

优先队列

理论知识

MinPQ(最小优先队列)是一种常见的数据结构,用于有效管理一组元素,其中最小元素可以快速被检索和删除。这种数据结构广泛应用于各种算法中,包括图算法(如 Dijkstra 的最短路径算法和 Prim 的最小生成树算法)、事件驱动的模拟、调度任务等。

MinPQ 的核心操作

MinPQ 主要支持以下几种操作:

  1. 插入(Insert) - 将一个新元素添加到优先队列中。
  2. 查找最小(Find Minimum) - 获取优先队列中的最小元素,但不从队列中删除它。
  3. 删除最小(Delete Minimum) - 移除并返回优先队列中的最小元素。
  4. 判断是否为空(IsEmpty) - 检查优先队列是否为空。
  5. 大小(Size) - 返回优先队列中的元素数量。

MinPQ 的实现方式

MinPQ 可以用多种方式实现,其中最常见的是使用二叉堆(Binary Heap)结构,特别是最小堆。最小堆是一个完全二叉树,可以用数组来有效表示,具有以下性质:

  • 每个节点的值都小于或等于其子节点的值。
  • 树是完全填满的,除了最底层,最底层从左向右填充,直到填满。

使用最小堆的优势

使用最小堆实现 MinPQ 的优势在于其操作的高效性:

  • 插入操作删除最小操作的时间复杂度为 O(log n),其中 n 是队列中的元素数量。
  • 查找最小操作的时间复杂度为 O(1),因为最小元素总是位于堆的根部。

应用示例

在许多实时系统和性能要求高的环境中,MinPQ 用来保证重要任务优先处理,或确保数据的最小值可以迅速访问。例如,在网络路由算法中,需要快速找到最短的未处理路径;在模拟环境中,优先处理最早发生的事件。

总的来说,MinPQ 是一种非常实用的数据结构,通过最小堆实现可以提供高效的性能,适用于需要快速访问和删除最小元素的各种应用场景。

在这里插入图片描述

实验数据

tinyPQ.txt测试数据内容

P Q E - X A M - P L E -

算法流程

在这里插入图片描述

代码实现

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;public class myMinPQ<Key extends Comparable<Key>> {private Key[] pq;private int n = 0;public myMinPQ(int initN){pq = (Key[]) new Comparable[initN+1];}public myMinPQ(){this(1);}public myMinPQ(Key[] keys){n = keys.length;pq = (Key[]) new Comparable[n+1];}private void resize(int capacity) {Key[] temp = (Key[]) new Comparable[capacity];for (int i = 1; i <= n; i++) {temp[i] = pq[i];}pq = temp;}public boolean isEmpty(){return n == 0;}public int size(){return n;}public void insert(Key v){pq[++n] = v;if (n == pq.length - 1) resize(2 * pq.length);swim(n);}public Key delMin(){Key min = pq[1];exch(1,n--);pq[n+1] = null;sink(1);if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);return min;}private boolean greater(int i, int j){return pq[i].compareTo(pq[j]) > 0;}private void exch(int i, int j){Key t = pq[i]; pq[i]=pq[j]; pq[j]=t;}private void swim(int k){while(k>1 && greater(k/2, k)) {exch(k/2,k);k=k/2;}}private void sink(int k){while(2*k <= n){int j = 2*k;if(j < n && greater(j, j+1)) j++;if(!greater(k,j)) break;exch(k,j);k = j;}}public static void main(String[] args) {myMinPQ<String> pq = new myMinPQ<String>();while (!StdIn.isEmpty()) {String item = StdIn.readString();if (!item.equals("-")) pq.insert(item);else if (!pq.isEmpty()) StdOut.print(pq.delMin() + " ");}StdOut.println("(" + pq.size() + " left on pq)");}
}

代码讲解

这段 Java 代码定义了一个名为 myMinPQ 的类,实现了一个最小优先队列(Min Priority Queue)。这个优先队列使用最小堆来维护元素的顺序,以确保能够快速地插入新元素并删除最小元素。下面是对这段代码各部分的详细解释:

类定义和泛型

  • myMinPQ<Key extends Comparable<Key>>: 类定义使用泛型 Key,这意味着队列中的元素必须实现 Comparable 接口,使得元素之间可以比较大小。

字段

  • private Key[] pq;: 存储堆元素的数组。数组从索引1开始使用,以简化父节点和子节点的索引计算。
  • private int n = 0;: 表示堆中元素的数量。

构造函数

  • myMinPQ(int initN): 接受一个初始容量 initN 并创建一个容量为 initN + 1 的数组。
  • myMinPQ(): 无参构造函数,默认初始化容量为1。
  • myMinPQ(Key[] keys): 接受一个数组 keys 并用其初始化优先队列。

方法

  • resize(int capacity): 当数组容量不足以存储更多元素时,调用此方法以调整数组大小。
  • isEmpty(): 检查优先队列是否为空。
  • size(): 返回队列中的元素数量。
  • insert(Key v): 向优先队列中插入一个新元素。使用 swim 方法确保最小堆的属性。
  • delMin(): 从队列中删除并返回最小元素。使用 sink 方法调整堆以维持最小堆的属性。
  • greater(int i, int j): 比较堆中索引 ij 的元素大小。
  • exch(int i, int j): 交换堆中索引 ij 的元素。
  • swim(int k): 上浮操作,调整元素位置以维持堆的顺序。
  • sink(int k): 下沉操作,调整元素位置以维持堆的顺序。

主函数

  • main(String[] args): 主函数从标准输入读取字符串,插入到优先队列中。如果读取到的字符串是 "-" 并且队列不为空,则删除并打印最小元素。最终打印队列中剩余元素的数量。

这个类的实现利用了二叉堆的特性,确保每次插入和删除操作的时间复杂度为 O(log n),从而使得操作效率较高。通过调整数组大小的方式,该实现还可以动态地调整内存使用,以适应不同的使用场景。

实验

代码编译

$ javac myMinPQ.java

代码运行

$ java myMinPQ < data\tinyPQ.txt
E A E (6 left on pq)

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【雅思写作】刘洪波——《最简化雅思写作2.0》笔记——【1. 概述篇】第一章:一些预备知识、第二章:谁对中国考生的写作低分负责

文章目录 第一章 一些预备知识考试类型大作文议论文&#xff08;Argumentation 80%&#xff09;报告&#xff08;Report 20%&#xff09;评分标准写作流程其他格式缩写数字标点符号英式和美式拼写I, My, We, You的使用范文背诵反模板时代机经与预测 第二章 谁对中国考生的写作低…

车载电子电器架构 —— 应用软件开发(中)

车载电子电器架构 —— 应用软件开发(中) 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明…

二、SPI协议

文章目录 总述1.SPI接口2. SPI工作模式3. SPI通信时序4. SPI协议 对比 UART协议&#xff08;上一篇文章刚介绍过uart协议&#xff0c;这里来对比一下&#xff09; 总述 SPI&#xff08;Serial Peripheral Interface&#xff09;是一种高速的、全双工、同步的串行通信总线&…

详解分布式锁

知识点&#xff1a; 单体锁存在的问题&#xff1a; 单体锁&#xff0c;即单体应用中的锁&#xff0c;通过加单体锁&#xff08;synchronized或RentranLock&#xff09;可以保证单个实例并发安全 单体锁是JVM层面的锁&#xff0c;只能保证单个实例上的并发访问安全 如果将单…

基于springboot实现疾病防控综合系统项目【项目源码+论文说明】

基于springboot实现疾病防控综合系统演示 摘要 在如今社会上&#xff0c;关于信息上面的处理&#xff0c;没有任何一个企业或者个人会忽视&#xff0c;如何让信息急速传递&#xff0c;并且归档储存查询&#xff0c;采用之前的纸张记录模式已经不符合当前使用要求了。所以&…

浅谈云计算资源和服务

目录 前言 正文 专有名词及其首字母缩写 轻量级应用服务器 云服务器ECS 专有网络VPC 其他类服务 尾声 &#x1f52d; Hi,I’m Pleasure1234&#x1f331; I’m currently learning Vue.js,SpringBoot,Computer Security and so on.&#x1f46f; I’m studying in University o…

如何在您的WordPress网站上安装和设置W3 Total Cache

本周有一个客户&#xff0c;购买Hostease的虚拟主机&#xff0c;询问我们的在线客服&#xff0c;如何在您的WordPress网站上安装和设置W3 Total Cache&#xff1f;我们为用户提供相关教程&#xff0c;用户很快解决了遇到的问题。在此&#xff0c;我们分享这个操作教程&#xff…

Agent AI智能体的未来:无限可能

文章目录 终结者智能体正反影响自我意识开放心态 终结者 还记得那场人类与天网之间的史诗般的战斗吗&#xff1f;-- 《终结者》系列电影。 《终结者》系列电影是一部标志性的科幻动作系列&#xff0c;以紧张刺激的情节、令人难忘的角色和开创性的视觉效果而闻名。 电影探讨了…

【智能优化算法】矮猫鼬优化算法(Dwarf Mongoose Optimization Algorithm,DMHO)

矮猫鼬优化算法(Dwarf Mongoose Optimization Algorithm,DMHO)是期刊“COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING”&#xff08;IF 7.3&#xff09;的2022年智能优化算法 01.引言 矮猫鼬优化算法(Dwarf Mongoose Optimization Algorithm,DMHO)模仿矮猫鼬的觅食行…

天府锋巢直播产业基地构建成都电商直播高地

天府锋巢直播产业基地自成立以来&#xff0c;一直秉承着创新、协同、共赢的发展理念&#xff0c;吸引了众多直播企业纷纷入驻。随着直播产业的迅猛发展&#xff0c;改成都直播基地内的配套服务也显得尤为重要。本文将深入探讨入驻天府锋巢直播产业基地后&#xff0c;配套的直播…

找不到msvcp140.dll无法执行代码的原因分析及修复方法

当用户在尝试运行某些应用程序或游戏时&#xff0c;可能会遇到系统弹出错误提示&#xff0c;显示“找不到msvcp140.dll无法执行代码”这一错误信息&#xff0c;它会导致程序无法正常启动。为了解决这个问题&#xff0c;我经过多次尝试和总结&#xff0c;找到了以下五种解决方法…

第十三届蓝桥杯决赛(国赛)真题 Java C 组【原卷】

文章目录 发现宝藏试题 A: 斐波那契与 7试题 B: 小蓝做实验试题 C: 取模试题 D: 内存空间试题 E \mathrm{E} E : 斐波那契数组试题 F: 最大公约数试题 G: 交通信号试题 I: 打折试题 J: 宝石收集 发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#x…

如何在 CentOS 上安装并配置 Redis

如何在 CentOS 上安装并配置 Redis 但是太阳&#xff0c;他每时每刻都是夕阳也都是旭日。当他熄灭着走下山去收尽苍凉残照之际&#xff0c;正是他在另一面燃烧着爬上山巅散烈烈朝晖之时。 ——史铁生 环境准备 本教程将在 CentOS 7 或 CentOS 8 上进行。确保你的系统已更新到最…

【数据结构】队列详解(Queue)

文章目录 有关队列的概念队列的结点设计及初始化队列的销毁判空和计数入队操作出队操作 有关队列的概念 队列:只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c;队列具有先进先出FIFO(First In First Out)入队列:进行插入操作的一端…

【C++】详细版 RAII技术的应用之智能指针(智能指针发展历程和简单模拟实现介绍)

目录 前言 一、智能指针有什么用&#xff1f; 二、什么是RAII(智能指针的底层思想)&#xff1f; 三、智能指针的发展历程以及模拟实现 1.auto_ptr&#xff08;C98&#xff09; 2.unique_ptr&#xff08;C11&#xff09; 3.shared_ptr&#xff08;C11&#xff09; 前言 C中…

Linux修炼之路之初识操作系统+基础指令(1)

目录 引言 一&#xff1a;对操作系统(OS)的简单了解 1.操作系统(OS) 是什么 2.操作系统好坏的衡量标准 3.操作系统存在的重要性 4.理解所有在计算机上的操作 二&#xff1a;Linux与windows操作的特点区别 三&#xff1a;基础指令 1.ls 指令 1.使用 2.常用选项 2.…

2024-AIDD-人工智能药物设计-AlphaFold3

AlphaFold3&#xff5c;万字长文解读 AlphaFold3预测所有分子相互作用准确结构 AlphaFold3 自2021年AlphaFold2问世以来&#xff0c;科研工作者们便开始利用这一蛋白结构预测模型来详细描绘众多蛋白质的结构、探索新药。近日&#xff0c;Google DeepMind公司推出了其最新产品…

关于JAVA-JSP电子政务网实现参考论文(论文 + 源码)

【免费】关于JAVA-JSP电子政务网.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89292355关于JAVA-JSP电子政务网 摘 要 当前阶段&#xff0c;伴随着社会信息技术的快速发展&#xff0c;使得电子政务能够成为我国政府职能部门进行办公管理的一个重要内容&#x…

日本OTC机械手维修需要注意哪些问题呢?

随着工业4.0时代的到来&#xff0c;机器人在制造业中的应用越来越广泛。OTC&#xff08;Over The Counter&#xff09;机器人作为工业机器人的一种&#xff0c;以其高效、精准、稳定的特点受到众多企业的青睐。然而&#xff0c;在实际使用过程中&#xff0c;可能会出现一些OTC机…

每日一题——力扣27. 移除元素(举一反三)

题目链接&#xff1a;https://leetcode.cn/problems/remove-element/description/ 菜鸡写法&#xff1a; // 函数定义&#xff0c;移除数组nums中所有值为val的元素&#xff0c;并返回新的数组长度 int removeElement(int* nums, int numsSize, int val) {// 如果数组长度为…