javascript - 堆和优先级队列是数据结构还是抽象数据类型？

Question

我见过类似的问题并阅读了很多答案。有人会认为我当时就知道了，但有些答案是矛盾的，现在我比开始时更困惑。

我的任务始于 - 堆和优先级队列之间有什么区别。在那里我了解到堆是一种数据结构，而优先级队列是一种抽象数据类型。但为什么呢？

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

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

有人可以概括地解释一下什么是数据结构和抽象数据类型吗？

Answer 1

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

一个Heap是一种数据结构，它存储数据的方式以及如何使用数据都有明确的定义。

使用堆来实现优先级队列是一个好主意，因为堆对数据的操作方式与优先级队列的工作方式非常一致。如果您检查documentation对于java.util.PriorityQueue，您将看到以下注释:

An unbounded priority queue based on a priority heap

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

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