java中的PriorityQueue类过程详解

一、什么是优先级队列

1、概念

我们都知道队列，队列的核心思想就是先进先出，这个优先级队列有点不太一样。优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序。（顺序有两种形式：升序或者是降序）

来一个标准点的定义：

PriorityQueue类在Java1.5中引入。PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

比如我们往队列里面插入132，插入2的时候，就会在内部调整为123（默认顺序是升序）。正是由于这个优良特性可以帮助我们实现一系列问题。我们先看一个例子，体会一下他的优点，然后再看一下为什么能够实现这样的功能。

我们看到就算是我们随意插入数据，但是输出的结果总是有序的，这样一来优先级队列就可以有了很多个使用场景。下面给出一道力扣题。体会一下他的优点。

2、案例演示特性

LeetCode215题：在未排序的数组中找到第 k个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入：3,2,3,1,2,4,5,5,6，k = 4。输出就是5，因此重复的并不考虑。我们一般情况下一般首先想到冒泡排序。每一次都冒出来一个最小的元素，这样冒K次，就是我们想要的结果。

其实冒泡排序还可以解决另外一个问题，那就是返回倒数第K大的元素，方法是每次冒出来一个最大的元素即可。

这样做很简单，但是需要我们自己手写冒泡排序，下面我们看使用优先级队列如何解决的。

就这几行代码就搞定了，是不是超级简单。为什么优先级队列能够实现呢？下面我们来分析一下他的数据结构：

3、数据结构

优先级队列底层的数据结构其实是一颗二叉堆，什么是二叉堆呢？我们来看看

在这里我们会发现以下特征：

（1）二叉堆是一个完全二叉树

（2）根节点总是大于左右子节点（大顶堆），或者是小于左右子节点（小顶堆）。

如果我们要插入一个节点怎么办呢？

自己使用画图工具画的，能看懂就行，不要在意那些细节兄弟。过程如下：

（1）找到待插入位置：满足完全二叉树的特点，依次插入

（2）插入之后判断是否满足二叉堆的性质，不满足那就调整

（3）1<>6交换，发现不满足，1<>4交换，满足即停止。

对于我们的优先级队列就是这样的一种数据结构，因此我们在插入的时候保证了数据的有序性。

OK。到这基本上我们能够体会到优先级队列的思想了。来一个小结：

优先级队列使用二叉堆的特点，可以使得插入的数据自动排序（升序或者是降序）。

到此这篇关于java中的PriorityQueue类的文章就介绍到这了,更多相关java PriorityQueue类内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！