Java堆结构PriorityQueue实现

2023-12-28 10:32

本文主要是介绍Java堆结构PriorityQueue实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在堆排序这篇文章中千辛万苦的实现了堆的结构和排序,其实在Java 1.5版本后就提供了一个具备了小根堆性质的数据结构也就是优先队列PriorityQueue。下面详细了解一下PriorityQueue到底是如何实现小顶堆的,然后利用PriorityQueue实现大顶堆。

PriorityQueue的数据结构

这里写图片描述

PriorityQueue的逻辑结构是一棵完全二叉树,存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。

PriorityQueue的操作

①add(E e) 和 offer(E e) 方法

add(E e) 和 offer(E e) 方法都是向PriorityQueue中加入一个元素,其中add()其实调用了offer()方法如下:

public boolean add(E e) {return offer(e);}

下面主要看看offer()方法的作用: 
这里写图片描述 
如上图调用 offer(4)方法后,往堆中压入4然后从下往上调整堆为小顶堆。offer()的代码实现:

public boolean offer(E e) {if (e == null)throw new NullPointerException();//如果压入的元素为null 抛出异常      int i = size;if (i >= queue.length)grow(i + 1);//如果数组的大小不够扩充size = i + 1;if (i == 0)queue[0] = e;//如果只有一个元素之间放在堆顶elsesiftUp(i, e);//否则调用siftUp函数从下往上调整堆。return true;}

对上面代码做几点说明: 
①优先队列中不能存放空元素。 
②压入元素后如果数组的大小不够会进行扩充,上面的queue其实就是一个默认初始值为11的数组(也可以赋初始值)。 
③offer元素的主要调整逻辑在 siftUp ( i, e )函数中。下面看看 siftUp(i, e) 函数到底是怎样实现的。

private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (key.compareTo((E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = key;}

上面的代码还是比较简明的,就是当前元素与父节点不断比较如果比父节点小就交换然后继续向上比较,否则停止比较的过程。

② poll() 和 remove() 方法 
poll 方法每次从 PriorityQueue 的头部删除一个节点,也就是从小顶堆的堆顶删除一个节点,而remove()不仅可以删除头节点而且还可以用 remove(Object o) 来删除堆中的与给定对象相同的最先出现的对象。先看看poll()方法。下面是poll()之后堆的操作

删除元素后要对堆进行调整: 
这里写图片描述

堆中每次删除只能删除头节点。也就是数组中的第一个节点。 
这里写图片描述 
将最后一个节点替代头节点然后进行调整。  


如果左右节点中的最小节点比当前节点小就与左右节点的最小节点交换。直到当前节点无子节点,或者当前节点比左右节点小时停止交换。

poll()方法的源码

public E poll() {if (size == 0)return null;//如果堆大小为0则返回null      int s = --size;modCount++;E result = (E) queue[0];E x = (E) queue[s];queue[s] = null;
//如果堆中只有一个元素直接删除        if (s != 0)siftDown(0, x);
//否则删除元素后对堆进行调整            return result;}

看看 siftDown(0, x) 方法的源码:

private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;int half = size >>> 1;        // loop while a non-leafwhile (k < half) {int child = (k << 1) + 1; // assume left child is leastObject c = queue[child];int right = child + 1;if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)c = queue[child = right];if (key.compareTo((E) c) <= 0)break;queue[k] = c;k = child;}queue[k] = key;}

siftDown()方法就是从堆的第一个元素往下比较,如果比左右孩子节点的最小值小则与最小值交换,交换后继续向下比较,否则停止比较。 
remove(4)的过程图: 
这里写图片描述 
先用堆的最后一个元素 5 代替4然后从5开始向下调整堆。这个过程和poll()函数一样,只不过poll()函数每次都是从堆顶开始。 
remove(Object o)的代码:

 public boolean remove(Object o) {int i = indexOf(o);//先在堆中找到o的位置if (i == -1)return false;//如果不存在则返回false。    else {removeAt(i);//否则删除数组中第i个位置的值,调整堆。return true;}}

removeAt(int i)的代码

 private E removeAt(int i) {assert i >= 0 && i < size;modCount++;int s = --size;if (s == i) // removed last elementqueue[i] = null;else {E moved = (E) queue[s];queue[s] = null;siftDown(i, moved);if (queue[i] == moved) {siftUp(i, moved);if (queue[i] != moved)return moved;}}return null;}

使用PriorityQueue实现大顶堆

PriorityQueue默认是一个小顶堆,然而可以通过传入自定义的Comparator函数来实现大顶堆。如下代码:

 private static final int DEFAULT_INITIAL_CAPACITY = 11;
PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(DEFAULT_INITIAL_CAPACITY, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {                return o2-o1;}});

实现了一个初始大小为11的大顶堆。这里只是简单的传入一个自定义的Comparator函数,就可以实现大顶堆了。

这篇关于Java堆结构PriorityQueue实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/545645

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听