堆是抽象数据类型吗？如果是这样，那么优先队列呢？ [英] Is heap an abstract data type? If so, what about priority queues?
问题描述
我读到优先级队列是堆数据结构的抽象数据类型，或者换句话说，堆是优先级队列的实现。但令我感到困惑的是，我将堆本身视为ADT，因为它们通常是使用数组来实现的（此处讨论最小/最大堆）。在ADT领域中，有人可以给我一个明显的区别吗？
I read that priority queue is an abstract data type for heap data structure or to put it in another way, heap is an implementation for priority queues. But what confuses me is that I see heap in itself as an ADT since they're normally implemented using arrays (talking about min/max heaps here). Could someone give me a clear distinction among the three within the realm of ADT?
推荐答案
让我分两个步骤回答您。.
Let me answer you in two steps..
数据类型是一组值以及对该类型的操作。
几乎所有名词都可以产生数据类型。
Data type is a set of values together with operations on that type. Almost any noun can give rise to a data type.
示例：整数，日期，字符串，复数，段落，债券，图片，集，包，向量，列表，堆栈，队列，双端队列，优先级队列，环，字典，树，图。
Example: integer, date, string, complex number, paragraph, bond, image, set, bag, vector, list, stack, queue, deque, priority queue, ring, dictionary, tree, graph.
有多种结构从技术上讲是数据类型，但它们是低级从某种意义上说，它们的操作是部分指定的。举例来说，二进制搜索树实施可被称为实施。通过向左和向右导航来执行查找，插入和删除的集合。 —但是左和右的含义取决于树中的项目是存储在数组中还是链接在一起。
There are a variety of constructs which are technically data types but are "low-level" in the sense that their operations are partially specified. For example, a binary search tree "implements" a set by performing lookups, insertions and deletions by "navigating left and right" — but the meanings of left and right depend on whether the items in the tree are stored in an array or are linked together.
例如：二进制搜索树， AVL树，B树，堆，配对堆，哈希表，展开树，特里树，R树
Example: binary search tree, AVL tree, B-tree, heap, pairing heap, hashtable, splay tree, trie, R-tree
ii）结论有关您的问题
两个优先级队列&堆是数据类型（更准确；抽象数据类型或 ADT ），但是由于堆是由优先级队列实现的，因此我们可以将其视为数据结构。
ii) Conclusion regard to your question
both priority queues & heaps are data types (more accurate; abstract data type or ADT) but because heap Implemented by priority queues, we can consider it data structure.
堆是一种抽象数据类型的最大有效实现，称为优先级队列，实际上，优先级队列通常被称为堆，而与如何实现无关。注意，尽管名称堆相似， 堆叠术语队列和队列，后两种是抽象数据类型，而堆是特定的数据结构，优先级队列和队列是特定的数据结构。是抽象数据类型的恰当术语。
The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact priority queues are often referred to as "heaps", regardless of how they may be implemented. Note that despite the similarity of the name "heap" to "stack" and "queue", the latter two are abstract data types, while a heap is a specific data structure, and "priority queue" is the proper term for the abstract data type.
注意：我的回答来自以下引用：
Note: my answer comes from below references:
- http://cs.lmu.edu/~ray/notes/dtds/
- https://en.wikipedia.org/wiki/Data_type
这篇关于堆是抽象数据类型吗？如果是这样，那么优先队列呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
