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

数据结构之堆练习题及PriorityQueue深入讲解!

题外话

上午学了一些JavaEE初阶知识,下午继续复习数据结构内容

正题

本篇内容把堆的练习题做一下

第一题

1.下列关键字序列为堆的是:( A )

A: 100,60,70,50,32,65  

B: 60,70,65,50,32,100  

C: 65,100,70,32,50,60

D: 70,65,100,32,50,60  

E: 32,50,100,70,65,60  

F: 50,100,70,65,60,32

第一题解析

堆分为大根堆小根堆,

而且堆是完全二叉树,

只需要从上到下从左到右建立一个完全二叉树再判断是否是大根堆或者是小根堆即可

A 画出图是一个大根堆

其余画出图既不是大根堆也不是小根堆

第二题

2.已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,在此过程中,关键字之间的比较次数是( C )

A: 1     B: 2     C: 3   D: 4

第二题解析

先画图,然后运用堆的删除,将8和最后一个元素12交换位置删除,再调整位置变成小根堆计数关键字比较次数即可

12先和15,10比较,和10交换位置,然后再和16比较调整为小根堆,一共比较三次

第三题

3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是( C )

A: [3,2,5,7,4,6,8]

B: [2,3,5,7,4,6,8]

C: [2,3,4,5,7,8,6]

D: [2,3,4,5,6,7,8]

第三题解析

和第二题一样,先画图,0与8交换,然后调整为小根堆即可

结果为2,3,4,5,7,8,6

PriorityQueue

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,

PriorityQueue是线程不安全的

PriorityBlockingQueue是线程安全的

本文主要介绍PriorityQueue。

1.使用时必须导入PriorityQueue所在的包

import java.uitl.PriorityQueue;

2.PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常

3. 不能插入null对象,否则会抛出NullPointerException

4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容

5.PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素,如果需要大堆需要用户提供比较器

用比较器创建大根堆

先说下Prriority常用构造方法,

PriorityQueue() 创建一个空的优先级队列,默认容量是11

PriorityQueue(int initialCapacity) 创建一个初始容量为initialCapacity的优先级队列,注意: initialCapacity不能小于1,否则会抛IllegalArgumentException异常

PriorityQueue(Collection c) 用一个集合来创建优先级队列

我们可以自己传一个比较器,创建大根堆,代码如下

class IntCmp implements Comparator<Integer>

{    

@Override    

public int compare(Integer o1, Integer o2)

{        return o2.compareTo(o1) 

}

}

这样插入元素的时候都会是以大根堆的方式插入

相关练习题

第一题

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

第一题思路

1.创建一个大根堆,把数组前k个元素添加进去

2.因为是大根堆,用数组剩余元素与堆顶元素进行比较,堆顶元素是大根堆中最大的,如果比堆顶元素小就删除堆顶元素,插入当前数组元素,会自动调整为大根堆

3.当数组全部遍历完成,大根堆的k个元素就是最小的k个元素

第一题代码详解
 public int[] smallestK(int[] arr, int k) {//创建数组ret,容量为kint[] ret=new int[k];//如果数组为空,或者k小于等于0,说明根本找不到最小的k个元素,不合法if(arr==null||k<=0){//直接返回retreturn ret;}//创建优先级队列PriorityQueue,使用匿名内部类传入比较器PriorityQueue<Integer> p=new PriorityQueue<>(new Comparator<Integer>() {
//将比较器设置成满足大根堆的形式@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}});//添加前k个元素for (int i=0;i<k;i++){p.offer(arr[i]);}//比较k以后元素是否比堆顶元素小for (int i = k; i <arr.length ; i++) {int top=p.peek();//如果比堆顶元素小if (arr[i]<top){//删除堆顶元素p.poll();//添加当前数组元素p.offer(arr[i]);}}//最后将最小的k个元素传入数组ret中即可for (int i = 0; i < k; i++) {ret[i] = p.poll();}//返回retreturn ret;}

第二题

堆排序,从大到小排序

第二题思路

1.我们先考虑,堆排序是建立大根堆还是建立小根堆

2.大根堆我们能保证堆顶元素是整个堆中最大的,小根堆我们能保证堆顶元素是整个堆中最小的

3.我们只需要建立大根堆,然后将堆顶元素和最后一个元素交换,然后再大根堆排序,然后再让堆顶元素和堆尾没有交换过的元素一一交换,再大堆根排序即可

第二题代码详解

//向下调整(上一篇堆的博客写过)

private void siftDown(int parent,int len)
{int child=parent*2+1;
//child等于len不会进入循环while (child<len){if (child+1<len&&elem[child]<elem[child+1]){child=child+1;}if (elem[child]>elem[parent]){swap(parent,child);parent=child;child=parent*2+1;}else {break;}}}
//堆排序,从小到大排序
public void heapSort()
{
//让end保存最后一个元素下标int end=usedSize-1;
//当end>0的时候就需要排序,等于零说明不需要排序了while(end>0){
//交换堆顶和没有交换过的最后一个元素值swap(0,end);
//向下排序,将没交换的排序为大根堆,end下标位置不会进入排序siftDown(0,end);
//让末尾位置调整到前一个即可end--;}
}

小结

大家有什么意见可以在评论区说出来,我都会改进!!!

相关文章:

数据结构之堆练习题及PriorityQueue深入讲解!

题外话 上午学了一些JavaEE初阶知识,下午继续复习数据结构内容 正题 本篇内容把堆的练习题做一下 第一题 1.下列关键字序列为堆的是:( A ) A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60 D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 …...

MySQL——Linux安装包

一、下载安装包 MySQL下载路径&#xff1a; MySQL :: MySQL Downloads //默认下载的企业版MySQL 下载社区版MySQL MySQL :: MySQL Community Downloads 1、源码下载 2、仓库配置 3、二进制安装包 基于官方仓库安装 清华centos 软件仓库&#xff1a; Index of /cen…...

MySQL学习笔记(数据类型, DDL, DML, DQL, DCL)

Learning note 1、前言2、数据类型2.1、数值类型2.2、字符串类型2.3、日期类型 3、DDL总览数据库/表切换数据库查看表内容创建数据库/表删除数据库/表添加字段删除字段表的重命名修改字段名&#xff08;以及对应的数据类型&#xff09; 4、DML往字段里写入具体内容修改字段内容…...

Asible管理变量与事实——管理变量(1)

Ansible简介 Ansible支持利用变量来储存值&#xff0c;并在Ansible项目的所有文件中重复使用这些值。这可以简化项目的创建和维护&#xff0c;并减少错误的数量。 通过变量&#xff0c;您可以轻松地在Ansible项目中管理给定环境的动态值。例如&#xff0c;变量可能包含下面这些…...

【微服务】------微服务架构技术栈

目前微服务早已火遍大江南北&#xff0c;对于开发来说&#xff0c;我们时刻关注着技术的迭代更新&#xff0c;而项目采用什么技术栈选型落地是开发、产品都需要关注的事情&#xff0c;该篇博客主要分享一些目前普遍公司都在用的技术栈&#xff0c;快来分享一下你当前所在用的技…...

【SCI绘图】【小提琴系列1 python】绘制按分类变量分组的垂直小提琴图

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【小提琴系列1 python】绘制按分类变量分组的垂直小提琴图&#xff0c;文末附完整代码 小提琴图是一种常用的数据可视化工具…...

docker------docker入门

&#x1f388;个人主页&#xff1a;靓仔很忙i &#x1f4bb;B 站主页&#xff1a;&#x1f449;B站&#x1f448; &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;Linux &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#…...

终极数据传输隐秘通道

SOCKS5代理作为网络请求中介的高级形态&#xff0c;提供了一种方法&#xff0c;通过它&#xff0c;数据包在传达其最终目的地前&#xff0c;首先经过一个第三方服务器。这种代理的先进之处在于其对各种协议的支持&#xff0c;包括HTTP、FTP和SMTP&#xff0c;以及它的认证机制&…...

Qt中的事件与事件处理

Qt框架中的事件处理机制是其GUI编程的核心部分&#xff0c;它确保了用户与应用程序之间的交互能够得到正确的响应。以下是对Qt事件处理机制的详细讲解以及提供一些基本示例。 1. 事件与事件处理简介 事件&#xff1a;在Qt中&#xff0c;所有的事件都是从QEvent基类派生出来的&…...

中间件漏洞攻防学习总结

前言 面试常问的一些中间件&#xff0c;学习总结一下。以下环境分别使用vulhub和vulfocus复现。 Apache apache 文件上传 (CVE-2017-15715) 描述: Apache(音译为阿帕奇)是世界使用排名第一的Web服务器软件。它可以运行在几乎所有广泛使用的计算机平台上&#xff0c;由于其跨…...

HarmonyOS开发实例:【分布式数据管理】

介绍 本示例展示了在eTS中分布式数据管理的使用&#xff0c;包括KVManager对象实例的创建和KVStore数据流转的使用。 通过设备管理接口[ohos.distributedDeviceManager]&#xff0c;实现设备之间的kvStore对象的数据传输交互&#xff0c;该对象拥有以下能力 ; 1、注册和解除注…...

蓝桥杯——运动会

题目 n 个运动员参加一个由 m 项运动组成的运动会&#xff0c;要求每个运动员参加每个项目。每个运动员在每个项目都有一个成绩&#xff0c;成绩越大排名越靠前。每个项目&#xff0c;不同运功员的成绩不会相 同&#xff0c;因此排名不会相同。(但是不同项目可能成绩会相同) 每…...

如何搭建APP分发平台分发平台搭建教程

搭建一个APP分发平台可以帮助开发者更好地分发和管理他们的应用程序。下面是一个简要的教程&#xff0c;介绍如何搭建一个APP分发平台。 1.确定需求和功能&#xff1a;首先&#xff0c;确定你的APP分发平台的需求和功能。考虑以下几个方面&#xff1a; 用户注册和登录&#xff…...

【计算机专业必看】详细说明文件打开模式r,w,a,r+,w+,a+的区别和联系

文章目录 1、联系2、区别r&#xff08;只读&#xff09;w&#xff08;只写&#xff09;a&#xff08;追加&#xff09;r&#xff08;读写&#xff0c;文件必须存在&#xff09;w&#xff08;读写&#xff0c;文件不存在则创建&#xff0c;存在则清空&#xff09;a&#xff08;读…...

Db2数据库稳定性解决方案

常见的数据库查询或写入慢&#xff0c;一般有以下情况 1、数据库经常有删除或有大量查询&#xff0c;&#xff08;导致磁盘碎裂&#xff0c;数据库缓存堆积&#xff09; 2、数据量大&#xff0c;导致在查询或写入时&#xff0c;由于负载高&#xff0c;导致系统慢 3、业务代码…...

如何用Python编写简单的网络爬虫(页面代码简单分析过程)

一、什么是网络爬虫 在当今信息爆炸的时代&#xff0c;网络上蕴藏着大量宝贵的信息&#xff0c;如何高效地从中获取所需信息成为了一个重要课题。网络爬虫&#xff08;Web crawler&#xff09;作为一种自动化工具&#xff0c;可以帮助我们实现这一目标&#xff0c;用于数据分析…...

【随笔】Git 高级篇 -- 最近标签距离查询 git describe(二十一)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…...

【leetcode面试经典150题】7.买卖股票的最佳时机(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…...

个人求职简历(精选8篇)

HR浏览一份简历也就25秒左右&#xff0c;如果你连「好简历」都没有&#xff0c;怎么能找到好工作呢&#xff1f; 如果你不懂得如何在简历上展示自己&#xff0c;或者觉得怎么改简历都不出彩&#xff0c;那请你一定仔细读完。 互联网运营个人简历范文> 男 22 本科 AI简历…...

Ubuntu22.04安装Anaconda

一、下载安装包 下载地址&#xff1a;https://www.anaconda.com/download#Downloads 参考&#xff1a;Ubuntu下安装Anaconda的步骤&#xff08;带图&#xff09; - 知乎 下载Linux 64-Bit (x86) installer 二、安装 在当前路径下&#xff0c;执行命令&#xff1a; bash Ana…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

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

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

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...