data-structures - 堆是抽象数据类型吗？如果是这样，那么优先队列呢？

Question

我读到优先级队列是堆数据结构的抽象数据类型，或者换句话说，堆是优先级队列的一种实现。但让我感到困惑的是，我将堆本身视为一种 ADT，因为它们通常是使用数组实现的(这里谈论最小/最大堆)。有人能给我一个 ADT 领域内三者的明确区别吗？

Answer 1

让我分两步回答你..

i) 定义

数据类型 是一组值以及对该类型的操作。几乎任何名词都可以产生数据类型。

Example: integer, date, string, complex number, paragraph, bond, image, set, bag, vector, list, stack, queue, deque, priority queue, ring, dictionary, tree, graph.

从技术上讲，有多种构造是数据类型，但在它们的操作被部分指定的意义上是“低级”的。例如，二叉搜索树通过“左右导航”执行查找、插入和删除来“实现”一个集合——但左右的含义取决于树中的项是存储在数组中还是链接在一起在一起。

Example: binary search tree, AVL tree, B-tree, heap, pairing heap, hashtable, splay tree, trie, R-tree

ii) 关于你的问题的结论

优先队列和堆都是数据类型(更准确地说是抽象数据类型或者ADT)但是因为堆是由优先队列实现的，所以我们可以认为它是数据结构。

堆是一种称为优先级队列的抽象数据类型的最有效实现，事实上优先级队列通常被称为“堆”，无论它们是如何实现的。请注意，尽管名称“堆”与“堆栈”和“队列”相似，但后两者是抽象数据类型，而堆是一种特定的数据结构，“优先队列”是抽象数据的专有名词类型。

---

注意:我的回答来自以下引用资料:

1. http://cs.lmu.edu/~ray/notes/dtds/
2. https://en.wikipedia.org/wiki/Data_type