当前位置: 首页 > 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…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...