Java堆&优先级队列示例讲解(上)
作者:爱干饭的猿 发布时间:2023-04-09 11:09:59
标签:Java,堆,优先级队列
1. 二叉树的顺序存储
1.1 存储方式
使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。
一般只适合表示完全二叉树,这种方式的主要用法就是堆的表示。
因为非完全二叉树会有空间的浪费(所有非完全二叉树用链式存储)。
1.2 下标关系
已知双亲 (parent) 的下标,则:
左孩子 (left) 下标 = 2 * parent + 1;
右孩子 (right) 下标 = 2 * parent + 2;
已知孩子(不区分左右) (child) 下标,则:
双亲 (parent) 下标 = (child - 1) / 2;
2. 堆(heap)
2.1 概念
1. 堆逻辑上是一棵完全二叉树
2. 堆物理上是保存在数组中
3. 满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆
4. 反之,则是小堆,或者小根堆,或者最小堆
5. 堆的基本作用是,快速找集合中的 最值
2.2 操作-(下沉&上浮)本例是最大堆
元素下沉:
/**
* 下沉操作
*/
public void siftDown(int k){
//还存在子树
while (leftChild(k) < data.size()){
int j = leftChild(k);
//判断是否存在右子树且大于左子树的值
if(j+1 < data.size() && data.get(j+1) > data.get(j)){
j=j+1;
}
//此时j为左右子树最大值
//和当前节点比较大小
if(data.get(j) <= data.get(k)){
break;
}else {
swap(k,j);
k=j;
}
}
}
元素上浮:
/**
* 上浮操作
*/
// 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值
// 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值
private void siftUp(int k) {
while (k>0 && data.get(k)>data.get(parent(k))){
swap(k,parent(k));
k=parent(k);
}
}
其中swap方法是交换操作:
//交换三连
private void swap(int i,int j) {
int temp = data.get(j);
data.set(j,data.get(i));
data.set(i,temp);
}
堆化数组:
/**
* 将任意数组堆化
* @param arr
*/
public MaxHeap(int[] arr){
data = new ArrayList<>(arr.length);
// 1.先将arr的所有元素复制到data数组中
for(int i : arr){
data.add(i);
}
// 2.从最后一个非叶子结点开始进行siftDown
for (int i = parent(data.size()-1); i >=0 ; i--) {
siftDown(i);
}
}
图示:
以此数组为例:
// 调整前
int[] array = { 27,15,19,18,28,34,65,49,25,37 };
// 调整后
int[] array = { 15,18,19,25,28,34,65,49,27,37 };
时间复杂度分析:
最坏的情况即图示的情况,从根一路比较到叶子,比较的次数为完全二叉树的高度
即时间复杂度为 O(log(n))
2.3 建堆-完整代码(最大堆)
/**
* 基于整形最大堆实现
* 时根节点从0开始编号,若此时节点编号为k
* 左孩子为2k+1
* 右孩子为2k+2
* 父节点为(k-1)/2
*/
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
// 使用JDK的动态数组(ArrayList)来存储一个最大堆
List<Integer> data;
// 构造方法的this调用
public MaxHeap(){
this(10);
}
// 初始化的堆大小
public MaxHeap(int size){
data = new ArrayList<>(size);
}
/**
* 将任意数组堆化
* @param arr
*/
public MaxHeap(int[] arr){
data = new ArrayList<>(arr.length);
// 1.先将arr的所有元素复制到data数组中
for(int i : arr){
data.add(i);
}
// 2.从最后一个非叶子结点开始进行siftDown
for (int i = parent(data.size()-1); i >=0 ; i--) {
siftDown(i);
}
}
/**
* 向最大堆中增加值为Value的元素
* @param value
*/
public void add(int value){
//1.先直接加到堆的末尾
data.add(value);
//2.元素上浮操作
siftUp(data.size()-1);
}
/**
* 只找到堆顶元素值
* @return
*/
public int peekMax (){
if(isEmpty()){
throw new NoSuchElementException("heap is empty!connot peek");
}
return data.get(0);
}
/**
* 取出当前最大堆的最大值
*/
public int extractMax(){
// 取值一定注意判空
if(isEmpty()){
throw new NoSuchElementException("heap is empty!connot extract");
}
int max = data.get(0);
// 1.将数组末尾元素顶到堆顶
int lastValue =data.get(data.size()-1);
data.set(0,lastValue);
// 2.将数组末尾的元素删除
data.remove(data.size()-1);
// 3.进行元素的下沉操作
siftDown(0);
return max;
}
/**
* 下沉操作
*/
public void siftDown(int k){
//还存在子树
while (leftChild(k) < data.size()){
int j = leftChild(k);
//判断是否存在右子树且大于左子树的值
if(j+1 < data.size() && data.get(j+1) > data.get(j)){
j=j+1;
}
//此时j为左右子树最大值
//和当前节点比较大小
if(data.get(j) <= data.get(k)){
break;
}else {
swap(k,j);
k=j;
}
}
}
/**
* 上浮操作
*/
// 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值
// 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值
private void siftUp(int k) {
while (k>0 && data.get(k)>data.get(parent(k))){
swap(k,parent(k));
k=parent(k);
}
}
//交换三连
private void swap(int i,int j) {
int temp = data.get(j);
data.set(j,data.get(i));
data.set(i,temp);
}
//判读堆为空
public boolean isEmpty(){
return data.size() == 0;
}
//根据索引找父节点
public int parent(int k){
return (k-1)>>1;
}
//根据索引找左孩子
public int leftChild(int k){
return k<<2+1;
}
//根据索引找右孩子
public int rightChild(int k){
return k<<2+2;
}
@Override
public String toString() {
return data.toString();
}
}
ps:随机数操作
int[] data=new int[10000];
//随机数
ThreadLocalRandom random = ThreadLocalRandom.current();
for (int i = 0; i < data.length; i++) {
data[i] = random.nextInt();
}
3. 优先级队列
详见下节:Java堆&优先级队列示例讲解(下)
来源:https://blog.csdn.net/m0_62218217/article/details/123279819
0
投稿
猜你喜欢
- 这是一个可以从乱码文本中得到正确的原始文本的程序,其基于的原理在于错误的编码往往导致位补充,因此正确的文本使用的字节数应该是最少的(之一)。
- Maven中建立的依赖管理方式基本已成为Java语言依赖管理的事实标准,Maven的替代者Gradle也基本沿用了Maven的依赖管理机制。
- 这是之前软工课设我写的java访问mysql工具类,它经过了多轮的测试,应该能够适应大多数的操作需求。比之前大二写的更鲁棒,更易用。pack
- 介绍该系统有三个角色,分别是:普通用户、房屋中介、管理员。普通用户的功能:浏览房屋信息、预约看房、和中介聊天、申请成为中介等等。房屋中介的功
- 1.docker安装seata 1.3.0镜像docker pull seataio/seata-server:1.3.02.运行容器获取配
- 简介Java内存模型是在硬件内存模型上的更高层的抽象,它屏蔽了各种硬件和操作系统访问的差异性,保证了Java程序在各种平台下对内存的访问都能
- 什么是深度优先什么是深度,即向下,深度优先,即向下优先,一口气走到底,走到底发现没路再往回走。在算法实现上来讲,深度优先可以考虑是递归的代名
- MVC三层架构我们在刚刚成为程序员的时候,就会被前辈们 “教育” 说系统的设计要遵循 MVC(Model-View-Controller)架
- 本文实例为大家分享了java利用数组随机抽取幸运观众的具体代码,供大家参考,具体内容如下思想:首先将所有观众姓名生成数组,然后获取数组元素的
- 1.概念a.是个二叉树(每个节点最多有两个子节点)b.对于这棵树中的节点的节点值左子树中的所有节点值 < 根节点 < 右子树的所
- 前言在我们做后端服务Dao层开发,特别是大数据批量插入的时候,这时候普通的ORM框架(Mybatis、hibernate、JPA)就无法满足
- 弃用内容先来纠正一个误区。主要之前在版本更新介绍的时候,存在一些表述上的问题。导致部分读者认为这次的更新是Datasource本身初始化的调
- SpringDataJpa创建中间表//fetch=FetchType.EAGER 关闭懒加载 相当于hibernate中的lazy=fal
- 官方文档:https://developers.weixin.qq.com/miniprogram/dev/framework/open-a
- jdk中自带了很多工具可以用于性能分析,位于jdk的bin目录下,jvisualvm工具可以以图形化的方式更加直观的监控本地以及远程的jav
- 我们知道 Spring Boot 已经提供了一套默认的异常处理机制,但是 Spring Boot 提供的默认异常处理机制却并不一定适合我们实
- 前言Spring Cloud默认为Zuul编写并启用了一些过滤器,这些过滤器有什么作用呢?我们不妨按照@EnableZuulServer、@
- Spark_SQL性能调优众所周知,正确的参数配置对提升Spark的使用效率具有极大助力,帮助相关数据开发、分析人员更高效地使用Spark进
- 问题描述:在用fabric集成后编译出现如下错误,Error:Cause: hostname in certificate didn'
- 之前一篇文章中我们讲了基于Mysql8的读写分离(文末有链接),这次来说说分库分表的实现过程。概念解析垂直分片按照业务拆分的方式称为垂直分片