Heap和Priority Queue是数据结构还是抽象数据类型？

Question

我看过类似的问题，也看了很多答案。有人会认为我当时就知道了，然而有些答案是矛盾的，现在我比刚开始时更加困惑。

我的探索始于 - 堆和优先级队列之间的区别是什么。我了解到 Heap 是一种数据结构，而 Priority Queue 是一种抽象数据类型。但是为什么？

到目前为止我发现这个答案是最好的：简单地说，数据结构和抽象数据类型之间的关系就像算法和伪代码之间的关系一样。第一个是一个想法，第二个是正式的描述（抽象的，难以理解的）。

有人提到 ADT 是一个依赖于语言的术语。因为它描述了“标准库中不包含的数据类型”。所以在Java或者JS中标准库中是没有Heap的，但是之前了解到堆是一种数据结构而不是抽象数据类型？

有人可以大致说明什么是数据结构和抽象数据类型吗？

Answer 1

一个Priority Queue是一种抽象数据类型，它可以用许多不同的方式实现。

Heap 是一种数据结构，它存储数据的方式及其使用数据的方式都有很好的定义。

使用堆来实现优先队列是个好主意，因为堆对数据的操作方式与优先队列的工作方式非常吻合。如果您在 documentation 中检查 java.util.PriorityQueue，您将看到以下评论：

An unbounded priority queue based on a priority heap

您可以将 ADT 视为高级逻辑描述（它的作用），而数据结构则准确定义了数据的存储和操作方式（它是如何完成的）。

你能用其他数据结构实现优先级队列吗？当然，可能效率不高。

Answer 2

如果您需要使用另一种数据结构来实现您想要的数据结构，那么您想要的数据结构最好描述为 抽象数据结构.

ADT 的一些例子是：

1. 堆栈
2. 队列
3. 双端队列
4. 优先队列
5. 树等

希望对您有所帮助。