java - Java PriorityQueue底层数据结构

Question

引用书Java: The Complete Reference , “Queue”接口(interface)扩展了“Collection”接口(interface)。此外，“PriorityQueue”扩展了“AbstractQueue”类并实现了“Queue”接口(interface)。

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

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

Answer 1

接口(interface)是“契约”，确保实现它们的类将提供特定的“行为”- 方法。

因此客户端代码(例如，将使用 PriorityQueue 的代码)将保证此类将具有仅从 Queue 实现中预期的行为。

换句话说:

List 接口(interface)具有可用于处理列表的方法。

Queue 接口(interface)具有可用于处理队列的方法。

PriorityQueue 实现了 List 接口(interface)的方法，使用起来会不舒服。

反之亦然，想象一下ArrayList 实现了Queue 接口(interface)——使用这样的东西会很困惑。

与您的问题更相关:Queue 接口(interface)可能有多个实现 - 在数组上、在 ArrayList 或 LinkedList 上具有不同的时间复杂度等等，但它们都将提供与 Queue 接口(interface)相同的一组方法。