上节介绍了堆的基本概念和算法,本节我们来探讨堆在Java中的具体实现类 - PriorityQueue。

我们先从基本概念谈起,然后介绍其用法,接着分析实现代码,最后总结分析其特点。

基本概念

顾名思义,PriorityQueue是优先级队列,它首先实现了队列接口(Queue),与LinkedList类似,它的队列长度也没有限制,与一般队列的区别是,它有优先级的概念,每个元素都有优先级,队头的元素永远都是优先级最高的。

PriorityQueue内部是用堆实现的,内部元素不是完全有序的,不过,逐个出队会得到有序的输出。

虽然名字叫优先级队列,但也可以将PriorityQueue看做是一种比较通用的实现了堆的性质的数据结构,可以用PriorityQueue来解决适合用堆解决的问题,下一节我们会来看一些具体的例子。

基本用法

Queue接口

PriorityQueue实现了Queue接口,我们在LinkedList一节介绍过Queue,为便于阅读,这里重复下其定义: