欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java优先队列 PriorityQueue详解(附图)

程序员文章站 2022-06-24 09:59:34
文章目录前言一、概念及应用场景二、原理及源码分析1. 了解继承图2. 优先队列的插入总结前言最近接触到优先队列的题目,正好趁这个机会复习一下优先队列,并深入了解一下源码。一、概念及应用场景PriorityQueue翻译过来是优先队列,是队列中的一种特殊队列。PriorityQueue里的元素是有序的,默认情况下是单调增,可以通过传入Comparator根据自己的需求来更改。在概念上,它是一个有序的二叉树,这种顺序的规则是(默认情况下),每个节点的值都比它的孩子节点的值小。一个最小堆如下图所示....


前言

最近接触到优先队列的题目,正好趁这个机会复习一下优先队列,并深入了解一下源码。


一、概念及应用场景

PriorityQueue翻译过来是优先队列,是队列中的一种特殊队列。PriorityQueue里的元素是有序的,默认情况下是单调增,可以通过传入Comparator根据自己的需求来更改。

在概念上,它是一个有序的二叉树,这种顺序的规则是(默认情况下),每个节点的值都比它的孩子节点的值小。一个最小堆如下图所示:
java优先队列 PriorityQueue详解(附图)只要符合每个节点的值都比它的孩子节点小即可。

在实现上,它使用数组来存储。因为该最小堆的是完全二叉树,所以按照每层从左向右的顺序存储,那么节点下标为 n 的孩子节点分别(2n+1)和(2n+2)为如上图的存储方式为:
java优先队列 PriorityQueue详解(附图)

应用场景

* 数据的操作为每次需要取最大值或最小值时

二、原理及源码分析

1. 了解继承图

java优先队列 PriorityQueue详解(附图)
以上是PriorityQueue属于集合框架下的类。它具有集合的特点,所以集合中的方法它能够使用。PriorityQueue继承自AbstractQueue,不允许插入null元素。

PriorityQueue继承自Queue, 所以在使用上 也继承了Queue的 offer()与poll()。鉴于PriorityQueue的 #有序 它重写了该方法

2. 优先队列的插入

为了保持PriorityQueue元素的有序性,在进行插入时,我们总是对插入后的数组做调整,这种调整的方式如下:

  • 首先将新增元素放到队尾
  • 将插入元素与它的父节点比较,如果父节点比元素大,将元素与父节点元素调换位置
  • 继续将该元素与父节点比较,直到该元素为根节点或比父节点的元素大为止

上述步骤如下图所示
java优先队列 PriorityQueue详解(附图)

这个时候得到的队列就是有序队列了。那我们来一起看看源码实现的方法吧!

以下是PriorityQueue的offer有关源码(jdk1.8):

 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;
        else
            siftUp(i, e);// 增加元素
        return true;
    }
private void siftUp(int k, E x) {
        if (comparator != null)   //传入了comparator 时
            siftUpUsingComparator(k, x);
        else     //没有传入comparator 时
            siftUpComparable(k, x);
    }
//传入了comparator时
private void siftUpUsingComparator(int k, E x) {
		//k刚开始为数组中现有元素的最后一个下标
        while (k > 0) {  
            int parent = (k - 1) >>> 1; //找到k所在位置的父节点下标
            Object e = queue[parent];
            //使用传入的comparator比较
            if (comparator.compare(x, (E) e) >= 0)  //比较元素大于父节点,则什么也不做
                break;
            //否则将两个值互换
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

没有传入comparator的与传入的同理,比较时使用的是默认的比大小方法:

// 没有传入comparator时
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;
    }

总结

PriorityQueue 作为有序队列能很好的解决每次去最大或最小元素的问题。以上就是优先队列的有关内容。

本文地址:https://blog.csdn.net/weixin_44780082/article/details/111991508