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

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

基于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…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...