个人中心
gpt4 book ai didi

解析Java中PriorityQueue优先级队列结构的源码及用法

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章解析Java中PriorityQueue优先级队列结构的源码及用法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

1、PriorityQueue的数据结构 。

JDK7中PriorityQueue（优先级队列）的数据结构是二叉堆。准确的说是一个最小堆.

二叉堆是一个特殊的堆， 它近似完全二叉树。二叉堆满足特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。 下图是一个最大堆 。

解析Java中PriorityQueue优先级队列结构的源码及用法

priorityQueue队头就是给定顺序的最小元素.

priorityQueue不允许空值且不支持non-comparable的对象。priorityQueue要求使用Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素.

priorityQueue的大小是无限制的（unbounded）, 但在创建时可以指定初始大小。当增加队列元素时，队列会自动扩容.

priorityQueue不是线程安全的， 类似的PriorityBlockingQueue是线程安全的.

我们知道队列是遵循先进先出（First-In-First-Out）模式的，但有些时候需要在队列中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue(优先队列)会很有帮助.

PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。 优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素.

优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象.

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加.

PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境.

2、PriorityQueue源码分析 。

成员:

?
1
2
priavte transient Object[] queue;
private int size = 0 ;

1.PriorityQueue构造小顶堆的过程 。

这里我们以priorityQueue构造器传入一个容器为参数PriorityQueue(Collecntion<? extends E>的例子:

构造小顶堆的过程大体分两步:

复制容器数据，检查容器数据是否为null 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
private void initElementsFromCollection(Collection<? extends E> c) {
   Object[] a = c.toArray();
   // If c.toArray incorrectly doesn't return Object[], copy it.
   if (a.getClass() != Object[]. class )
     a = Arrays.copyOf(a, a.length, Object[]. class );
   int len = a.length;
   if (len == 1 || this .comparator != null )
     for ( int i = 0 ; i < len; i++)
       if (a[i] == null )
         throw new NullPointerException();
   this .queue = a;
   this .size = a.length;
}

调整，使数据满足小顶堆的结构。 首先介绍两个调整方式siftUp和siftDown 。

siftDown: 在给定初始化元素的时候，要调整元素，使其满足最小堆的结构性质。因此不停地从上到下将元素x的键值与孩子比较并做交换，直到找到元素x的键值小于等于孩子的键值（即保证它比其左右结点值小），或者是下降到叶子节点为止。 例如如下的示意图，调整9这个节点:

解析Java中PriorityQueue优先级队列结构的源码及用法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void siftDownComparable( int k, E x) {
   Comparable<? super E> key = (Comparable<? super E>)x;
   int half = size >>> 1 ;    // size/2是第一个叶子结点的下标
   //只要没到叶子节点
   while (k < half) {
     int child = (k << 1 ) + 1 ; // 左孩子
     Object 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;
}

siftUp: priorityQueue每次新增加一个元素的时候是将新元素插入对尾的。因此，应该与siftDown有同样的调整过程，只不过是从下（叶子）往上调整。 例如如下的示意图，填加key为3的节点:

解析Java中PriorityQueue优先级队列结构的源码及用法

?
1
2
3
4
5
6
7
8
9
10
11
12
private void siftUpComparable( int k, E x) {
   Comparable<? super E> key = (Comparable<? super E>) x;
   while (k > 0 ) {
     int parent = (k - 1 ) >>> 1 ;   //获取parent下标
     Object e = queue[parent];
     if (key.compareTo((E) e) >= 0 )
       break ;
     queue[k] = e;
     k = parent;
   }
   queue[k] = key;
}

总体的建立小顶堆的过程就是:

?
1
2
3
4
private void initFromCollection(Collection<? extends E> c) {
     initElementsFromCollection(c);
     heapify();
   }

其中heapify就是siftDown的过程.

2.PriorityQueue容量扩容过程 。

从实例成员可以看出，PriorityQueue维护了一个Object[], 因此它的扩容方式跟顺序表ArrayList相差不多。 这里只给出grow方法的源码 。

?
1
2
3
4
5
6
7
8
9
10
11
private void grow( int minCapacity) {
     int oldCapacity = queue.length;
     // Double size if small; else grow by 50%
     int newCapacity = oldCapacity + ((oldCapacity < 64 ) ?
                      (oldCapacity + 2 ) :
                      (oldCapacity >> 1 ));
     // overflow-conscious code
     if (newCapacity - MAX_ARRAY_SIZE > 0 )
       newCapacity = hugeCapacity(minCapacity);
     queue = Arrays.copyOf(queue, newCapacity);
   }

可以看出，当数组的Capacity不大的时候，每次扩容也不大。当数组容量大于64的时候，每次扩容double.

3、PriorityQueue的应用 。

eg1： 这里给出一个最简单的应用：从动态数据中求第K个大的数。 思路就是维持一个size = k 的小顶堆.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//data是动态数据
//heap维持动态数据的堆
//res用来保存第K大的值
public boolean kthLargest( int data, int k, PriorityQueue<Integer> heap, int [] res) {
   if (heap.size() < k) {
     heap.offer(data);
     if (heap.size() == k) {
       res[ 0 ] = heap.peek();
       return true ;
     }
     return false ;
   }
   if (heap.peek() < data) {
     heap.poll();
     heap.offer(data);
   }
   res[ 0 ] = heap.peek();
   return true ;
}

    eg2： 我们有一个用户类Customer，它没有提供任何类型的排序。当我们用它建立优先队列时，应该为其提供一个比较器对象.

Customer.java 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.journaldev.collections;
 
public class Customer {
 
   private int id;
   private String name;
 
   public Customer( int i, String n){
     this .id=i;
     this .name=n;
   }
 
   public int getId() {
     return id;
   }
 
   public String getName() {
     return name;
   }
 
}

我们使用Java随机数生成随机用户对象。对于自然排序，我们使用Integer对象，这也是一个封装过的Java对象。 下面是最终的测试代码，展示如何使用PriorityQueue:

PriorityQueueExample.java 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.journaldev.collections;
 
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
 
public class PriorityQueueExample {
 
   public static void main(String[] args) {
 
     //优先队列自然排序示例
     Queue<Integer> integerPriorityQueue = new PriorityQueue<>( 7 );
     Random rand = new Random();
     for ( int i= 0 ;i< 7 ;i++){
       integerPriorityQueue.add( new Integer(rand.nextInt( 100 )));
     }
     for ( int i= 0 ;i< 7 ;i++){
       Integer in = integerPriorityQueue.poll();
       System.out.println( "Processing Integer:" +in);
     }
 
     //优先队列使用示例
     Queue<Customer> customerPriorityQueue = new PriorityQueue<>( 7 , idComparator);
     addDataToQueue(customerPriorityQueue);
 
     pollDataFromQueue(customerPriorityQueue);
 
   }
 
   //匿名Comparator实现
   public static Comparator<Customer> idComparator = new Comparator<Customer>(){
 
     @Override
     public int compare(Customer c1, Customer c2) {
       return ( int ) (c1.getId() - c2.getId());
     }
   };
 
   //用于往队列增加数据的通用方法
   private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
     Random rand = new Random();
     for ( int i= 0 ; i< 7 ; i++){
       int id = rand.nextInt( 100 );
       customerPriorityQueue.add( new Customer(id, "Pankaj " +id));
     }
   }
 
   //用于从队列取数据的通用方法
   private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
     while ( true ){
       Customer cust = customerPriorityQueue.poll();
       if (cust == null ) break ;
       System.out.println( "Processing Customer with ID=" +cust.getId());
     }
   }
 
}

注意我用实现了Comparator接口的Java匿名类，并且实现了基于id的比较器。 当我运行以上测试程序时，我得到以下输出:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Processing Integer:9
Processing Integer:16
Processing Integer:18
Processing Integer:25
Processing Integer:33
Processing Integer:75
Processing Integer:77
Processing Customer with ID=6
Processing Customer with ID=20
Processing Customer with ID=24
Processing Customer with ID=28
Processing Customer with ID=29
Processing Customer with ID=82
Processing Customer with ID=96

从输出结果可以清楚的看到，最小的元素在队列的头部因而最先被取出。如果不实现Comparator，在建立customerPriorityQueue时会抛出ClassCastException.

?
1
2
3
4
5
6
7
Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable
   at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
   at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
   at java.util.PriorityQueue.offer(PriorityQueue.java:329)
   at java.util.PriorityQueue.add(PriorityQueue.java:306)
   at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
   at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)

  。

最后此篇关于解析Java中PriorityQueue优先级队列结构的源码及用法的文章就讲到这里了,如果你想了解更多关于解析Java中PriorityQueue优先级队列结构的源码及用法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： 解析php中获取系统信息的方法
文章推荐： 解析PHP对现有搜索引擎的调用
文章推荐： Java 并发编程学习笔记之核心理论基础
文章推荐： java读取用户登入退出日志信息上传服务端
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com