【Java编程的逻辑】堆与优先级队列PriorityQueue

2024-09-07 15:18
文章标签 java 逻辑 编程 优先级 队列 priorityqueue

本文主要是介绍【Java编程的逻辑】堆与优先级队列PriorityQueue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完全二叉树 & 满二叉树 & 堆

基本概念

满二叉树是指除了最后一层外，每个节点都有两个孩子，而最后一层都是叶子节点，都没有孩子。
满二叉树

满二叉树一定是完全二叉树，但完全二叉树不要求最后一层是满的，但如果不满，则要求所有节点必须集中在最左边，从左到右是连续的，中间不能有空的。

完全二叉树

特点

在完全二叉树中，可以给每个节点一个编号，编号从1开始连续递增，从上到下，从左到右
完全二叉树编号

完全二叉树有一个重要的特点：给定任意一个节点，可以根据其编号直接快速计算出其父节点和孩子节点。如果编号为i，则父节点编号为i/2，左孩子编号为2*i，右孩子编号为2*i+1
它使得逻辑概念上的二叉树可以方便地存储到数组中，数组中的元素索引就对应节点的编号，树中的父子关系通过其索引关系隐含维持，不需要单独保持。
用数组表示完全二叉树

这种存储二叉树的方法与之前介绍的TreeMap是不一样的。在TreeMap中，有一个单独的内部类Entry，Entry有三个引用，分别指向父节点、左孩子、右孩子。使用数组存储的优点是节省空间，而且访问效率高。

堆

堆逻辑概念上是一棵完全二叉树，而物理存储上使用数组，还要一定的顺序要求。

TreeMap内部使用的是排序二叉树原理，排序二叉树是完全有序的，每个节点都有确定的前驱和后继，而且不能有重复元素。与排序二叉树不同，在堆中，可以有重复元素，元素间不是完全有序的，但对于父子节点直接，有一定的顺序要求。根据顺序分为两种堆：最大堆、最小堆

最大堆是指每个节点都不大于其父节点。这样，对于每个父节点，一定不小于其所有孩子节点，那么根节点就是所有节点中最大的了。最小堆与最大堆就正好相反，每个节点都不小于其父节点。

最大堆和最小堆

总结来说：堆是完全二叉树，父子节点间有特定顺序，分为最大堆和最小堆，堆使用数组进行物理存储。

堆的操作

添加元素

这里我们以最小堆为例进行讲解

如果堆为空，则直接添加一个根就行了。
如果堆不为空，要在其中添加元素，基本步骤为：
1. 添加元素到最后位置
2. 与父节点比较，如果大于等于父节点，则满足堆的性质，结束。否则与父节点进行交换，然后再与父节点比较和交换，直到父节点为空或者大于等于父节点。

该方法称为向上调整
添加一个元素，需要比较和交换的次数最多为树的高度，即log(N)。N为节点数

从头部删除元素

  1. 用最后一个元素替换头部元素，并删掉最后一个元素
  2. 将新的头部与两个孩子节点中较小的比较，如果不大于该孩子节点，则满足堆的性质，结束。否则与较小的孩子节点进行交换，交换后，再与较小的孩子节点比较，一直到没有孩子节点或者不大于两个孩子节点。

该方法称为向下调整

从中间删除元素

  1. 与从头部删除一样，先用最后一个元素替换待删元素。
  2. 有两种情况，如果该元素大于某孩子节点，则需要向下调整；如果小于父节点，则需要向上调整。

查找和遍历

在堆中进行查找没有特殊的算法，就是从数组的头找到尾，效率为O(N)

在堆中进行遍历也是类似的。

构建堆

给定一个无序数组，如何使之成为一个最小堆呢？
基本思路是：从最后一个非叶子节点开始，一直往前直到根，对每个节点，执行向下调整。换句话说，自底向上。先使每个最小子树为堆，然后对左右子树和其父节点合并，调整为更大的堆，因为每个子树已经为堆，所以调整就是堆父节点执行向下调整，这样一直合并调整到根。

小结

  1. 在添加和删除元素时，效率为O(logN)
  2. 查找和遍历元素，效率为O(N)
  3. 构建堆的效率是O(N)

PriorityQueue

PriorityQueue是优先级队列，实现了队列接口（Queue），内部是用堆实现的，内部元素不是完全有序的，不过，逐个出对会得到有序的输出。

基本用法

PriorityQueue有多个构造方法：

public PriorityQueue();
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
public PriorityQueue(Collection<? extends E> c);

PriorityQueue是用堆实现的，堆物理上就是数组，与ArrayList类似，都是使用动态数据，根据元素的个数进行动态扩展，initialCapacity表示初始化的数组大小，默认为11。与TreeMap/TreeSet类似，为了保持一定顺序，PriorityQueue要求要么元素实现Comparable接口，要么传递一个比较器Comparator。

实现原理

先看看内部组成成员： 

// 实际存储元素的数组
private transient Object[] queue;
// 当前元素个数
private int size = 0;
// 比较器，可以为null
private final Comparator<? super E> comparator;
// 修改次数
private transient int modCount = 0;

构造方法上面已经提到过了，主要是初始化queue和comparator 。 操作相关的代码和上面的堆的操作差不多的，这里我们以入队为例，做一个简单的讲解 

public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;// 确保数组长度是够的if (i >= queue.length)grow(i + 1);// 元素长度增加    size = i + 1;// 如果第一次添加，直接放在第一个位置if (i == 0)queue[0] = e;// 否则将其放入最后一个位置，并向上调整    elsesiftUp(i, e);return true;
}private void grow(int minCapacity) {int oldCapacity = queue.length;// Double size if small; else grow by 50% // 如果原来长度比较小，扩展为两倍，否则就增加50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);
}/*** 向上调整*/
private void siftUp(int k, E x) {// 如果有比较器就用比较器if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);
}/*** 向上寻找x真正应该插入的位置* @param k 表示插入的位置* @param x 表示新元素*/ 
private void siftUpUsingComparator(int k, E x) {while (k > 0) {// 父节点位置，当前节点位置/2int parent = (k - 1) >>> 1;// 父节点Object e = queue[parent];// 如果新元素大于等于父节点，则满足堆的性质，退出if (comparator.compare(x, (E) e) >= 0)break;// 否则父元素下移，继续向上寻找    queue[k] = e;k = parent;}queue[k] = x;
}

小结

  1. 实现了优先级队列，最先出对的总是优先级最高的
  2. 优先级可以有相同的，内部元素不是完全有序的
  3. 查看头部元素效率很高为O(1)，入队、出队效率较高为O(logN)，构建堆的效率为O(N)
  4. 查找和删除的效率比较低为O(N)

堆和PriorityQueue的应用

问题

这里先抛出两个比较常见的问题，然后再用堆的思想来进行解决
1. 求前K个最大的元素，元素个数不确定，数据量可能很大，甚至源源不断到来，但需要知道目前为止最大的前K个元素
2. 求中值元素，中值不是平均值，而是排序后中间那个元素的值，同样数据量可能很大，甚至源源不断到来

求前K个最大的元素

一个简单的思路是排序，排序后取最大的K个就可以了，排序可以使用Arrays.sort()方法，效率为O(N*log(N))。Arrays.sort()使用的是经过调优的快速排序法 。
另一种思路是选择，循环选择K次，每次从剩下的元素中选择最大值，效率为O(N*K)，如果K值大于log(N)，就不如排序了。

不过这两个思路都是假定所有元素都是已知的，而不是动态的。如果元素个数不确定，且源源不断到来呢？

一个基本的思路是维护一个长度为K的数组，最前面的K个元素就是目前最大的K个元素，以后每来一个新元素的时候，都先找到数组中最小值，将新元素与最小值相比，如果小于最小值，什么都不用做；如果大于最小值，则将最小值替换为新元素。
这类似于生活中常见的末尾淘汰。

这样，数组中维护的永远都是最大的K个元素，不管数据源有多少，需要的内存开销是固定的，就是长度为K的数组。不过，每来一个元素，都需要找最小值，都需要进行K次比较，能不能减少比较次数呢？

解决方法是使用最小堆维护这个K个元素，最小堆中，根即第一个元素永远都是最小的，新来的元素与根比较就可以了，如果小于根，则堆不需要变化，否则用新元素替换根，然后向下调整堆即可，调整的效率为O(logK)，总体效率就是O(N*logK)。而且使用了最小堆后，第K个最大的元素也很容易获取，它就是堆的根

public class TopK<E> {private PriorityQueue<E> p;private int k;public TopK(int k) {this.k = k;this.p = new PriorityQueue<>(k);}public void addAll(Collection<? extends E> c) {for(E e: c) {add(e);}}public void add(E e) {if(p.size() < k) {p.add(e);return ;}Comparable<? super E> head = (Comparable<? super E>)p.peek();if(head.compareTo(e)>0) {// 小于TopK中的最小值，不用变return ;}// 新元素替换掉原来最小值成为TopK之一p.poll();p.add(e);}public <T> T[] toArray(T[] a) {return p.toArray(a);}public E getKth() {return p.peek();}
}

求中值

中值就是排序后中间那个元素的值，如果元素个数为奇数，中值是没有歧义的，如果是偶数，可以为偏小的，也可以为偏大的。

一个简单的思路就是排序，排序后取中间的那个值就可以了。排序可以使用Arrays.sort()方法，效率为O(N*log(N))。
当然，这是要在数据源已知的情况下才能做到的。如果数据源源不断到来呢？

可以使用两个堆，一个最大堆，一个最小堆
1. 假设当前的中位数为m，最大堆维护的是<=m的元素，最小堆维护的是>=m的元素，但两个堆都不包含m。
2. 当新的元素到达时，比如为e，将e与m进行比较，若e<=m，则将其加入最大堆中，否则加入最小堆中
3. 如果此时最小堆和最大堆的元素个数相差>=2，则将m加入元素个数少的堆中，然后从元素个数多的堆将根节点移除并赋值给m。

给个示例解释一下，输入的元素依次是：34，90，67，45，1
1. 输入第一个元素时，m赋值为34
2. 输入第二个元素时，90>34，把90加入最小堆，m不变
3. 输入第三个元素时，67>34，把67加入最小堆，此时最小堆根节点为67。但是现在最小堆中元素个数为2，最大堆中元素个数为0，所以需要做调整，把m(34)加入个数少的堆中（最大堆），然后从元素个数多的堆（最小堆）将根节点移除并赋值给m，所以现在m为67，最大堆中有34，最小堆中有90
4. 输入第四个元素时，45<67，把45加入最大堆，m不变
5. 输入第五个元素时，1<67，把1加入最大堆中，此时m为67，最大堆中有1，34，45，最小堆中有90，所以需要调整。调整后，m为45，最大堆为1，34，最小堆为67，90。

public class Median<E> {// 最小堆private PriorityQueue<E> minP;// 最大堆private PriorityQueue<E> maxP;// 中值private E m;public Median() {this.minP = new PriorityQueue<>();this.maxP = new PriorityQueue<>(11, Collections.reverseOrder());}// 比较private int compare(E e, E m) {Comparable<? super E> cmpr = (Comparable<? super E>)e;return cmpr.compareTo(e);}public void add(E e) {if(m == null) {// 第一个元素m = e;return ;}        if(compare(e, m) < 0) {// 如果e小于m，则加入最大堆maxP.add(e);} else {// 如果e大于m，则加入最小堆minP.add(e);}if(minP.size() - maxP.size() >= 2) {// 最小堆中元素比最大堆中元素多2个// 将m加入最大堆中，然后将最小堆中的根移除赋值给mmaxP.add(this.m);this.m = minP.poll();} else if(maxP.size() - minP.size() >= 2) {minP.add(this.m);this.m = maxP.poll();}}public void addAll(Collection<? extends E> c) {for(E e : c) {add(e);}}public E getM() {return m;}
}

这篇关于【Java编程的逻辑】堆与优先级队列PriorityQueue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1145411。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

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

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

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

浅析Spring Security认证过程

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

Spring Security--Architecture Overview

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

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

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

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

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

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
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2