问题：

Java PriorityQueue的底层数据结构

夹谷飞龙

2023-03-14

参考《Java：完整参考》一书中的“队列”接口扩展了“集合”接口。此外，“PriorityQueue”扩展了“AbstractQueue”类并实现了“Queue”接口。

此外，根据Internet上的许多文章，考虑到O（logns）中的插入和删除，堆提供了最有效的优先级队列实现。作为完整的二叉树，堆可以简单地在数组/列表上实现。

我的问题是，如果堆对于优先级队列是有效的，那么为什么PriorityQueue使用Queue接口？为什么它不使用List接口？否则，实现的基本概念/思想是什么，提供与堆相同（或更好）的时间复杂度？

共有2个答案

皇甫夕

2023-03-14

因为PriorityQueue只是一个带有Heapify技术的Queue，以保证在插入/删除期间的良好性能。

堆的意思是Heapify技术

为什么PriorityQueue使用Heapify技术？

PriorityQueue的继承层次结构是什么？

public class PriorityQueue<E> extends AbstractQueue<E> {}

public abstract class AbstractQueue<E> extends AbstractCollection<E> {}

public abstract class AbstractCollection<E> implements Collection<E> {}

什么是List的继承层次结构？

public interface List<E> extends Collection<E> {}

为什么PriorityQueue不扩展List接口？

因为列表接口提供了优先级队列没有定义或需要的操作，比如获取（索引），而实现只是添加（）和轮询（），这与队列机制类似，队列机制是插入尾部并从头部轮询，而不是像ArrayList或LinkedList那样的顺序插入，它们扩展了列表接口。而且无法通过索引位置获取值。

PriorityQueue和Queue之间有什么区别？

PriorityQueue使用“Heapify”技术，可以是Min PQ或Max PQ，您可以在声明PriorityQueue的构造函数时简单地定义，而Queue只是将值添加到尾部并从头部轮询。

使用PriorityQueue有什么好处？

最大的好处是，您可以定义最小PQ或最大PQ，并以排序顺序获得元素，以时间复杂度O（log₂N）的升序或降序进行排序，这对于寻找最短路径、粒子碰撞检测等许多应用非常重要。

娄飞鸾

2023-03-14

接口是“契约”，它确保实现它们的类将提供某些“行为”方法。

因此，客户端代码（例如，将使用PriorityQueue的代码）将保证该类的行为可能仅来自Queue实现。

换句话说：

List界面提供了一些有用的方法来处理列表。

Queue接口具有对处理队列有用的方法。

PriorityQueue实现了一个List接口的方法，但使用起来不舒服。

反之亦然，想象一下实现Queue接口的ArrayList-使用这样的东西会很混乱。

与您的问题更相关的是：Queue接口可能有多种实现方式——在数组、在ArrayList或LinkedList上，它们的时间复杂度不同，等等，但它们都将提供相同的Queue接口方法集。

共有2个答案