堆是否被视为抽象数据类型？
Is Heap considered an Abstract Data Type?
我正在上数据结构课程，对什么被认为是 ADT（抽象数据类型）而什么不是（如果不是 ADT，那么它一定是实施？）。
具体来说，我说的是堆。
我在维基百科上读到“堆是一种专门的基于树的数据结构”这是否意味着它是一个 ADT？如果是这样，那么我无法理解同样来自维基百科的以下行 "The heap is one maximally efficient implementation of an abstract data type called a priority queue".
我的意思是，Heap 可以是一个 ADT 还是其他一些 ADT 的实现（在这种情况下是优先队列的实现？我理解 ADT 的概念，在二叉堆的上下文中我理解它可以使用数组实现，其中 arr[i] 是 arr[2i] 和 arr[2i + 1] 的父级
我只是对堆是否可以一方面是使用数组实现的 ADT 而另一方面是实现其他 ADT 的数据结构感到困惑。
想得到一些关于这个的澄清。
堆不被视为抽象数据类型。
堆是一种特殊的基于树的数据结构，它是称为优先队列的抽象数据类型的实现。
堆不是 ADT。它是一个数据结构。
强制性维基百科引用：
In computer science, an abstract data type (ADT) is a mathematical
model for data types where a data type is defined by its behavior
(semantics) from the point of view of a user of the data, specifically
in terms of possible values, possible operations on data of this type,
and the behavior of these operations. This contrasts with data
structures, which are concrete representations of data, and are the
point of view of an implementer, not a user.
奖励内容灵感来自 Steve McConnell 的代码完成 - 2。
数据结构是低级实现域项，与在问题域中工作的 ADT 形成对比。 ADT 让您可以操纵真实世界的实体，而不是低级的实现实体。您可以将单元格添加到电子表格、window 到 window 类型的新类型或火车上的另一位乘客，而不是将节点插入链表或将项目添加到堆模拟.
可以清楚的看到heap定义了insert(), heapify(), peek(), getTop()等语义——列在here细节。因此它是一个数据结构。
但是，如果您模拟俄罗斯方块游戏，其中添加一个新方块会简单地移动并坐在它掉落的任何地方的顶部，这个俄罗斯方块游戏的 UI 将实际上是一个ADT。
我会尝试以相反的方式澄清这种混淆。引用来自 here 的维基百科：
While priority queues are often implemented with heaps, they are
conceptually distinct from heaps. A priority queue is an abstract
concept like "a list" or "a map"; just as a list can be implemented
with a linked list or an array, a priority queue can be implemented
with a heap or a variety of other methods such as an unordered array.
因此堆只是优先级队列抽象数据类型 (ADT) 的一种实现，它可以在下面列出的许多其他类型中实现，但可能不限于：
- 无序数组
- 无序列表
- 有序数组
- 有序列表
- 二叉搜索树 (BST)
- 平衡二叉搜索树（AVL 树）
- 二叉堆（OP询问）
优先队列ADT中主要操作的堆实现与其他可能实现的时间效率比较：
----------------------------------------------------------------------------
| Implementation | Insertion | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1 | n | n
----------------------------------------------------------------------------
| Unordered List | 1 | n | n
----------------------------------------------------------------------------
| Ordered Array | n | 1 | 1
----------------------------------------------------------------------------
| Ordered List | n | 1 | 1
----------------------------------------------------------------------------
| BST | logn (avg.) | logn (avg.) | logn (avg.)
----------------------------------------------------------------------------
| Balanced BST | log n | log n | log n
----------------------------------------------------------------------------
| Binary Heaps | log n | log n | 1
我向您展示的是来自维基百科的完整行，而您只引用了混淆的行的一部分 you.maybe 如果您只读到行的下一部分，您会更好地理解它。
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. A common implementation of a heap is the binary heap, in which the tree is a binary tree
这里说
in fact priority queues are often referred to as "heaps", regardless of how they may be implemented.
由于堆数据结构（DS）的流行，在实现优先级队列时ADT.priority队列ADT通常被称为堆
在维基百科引用的下一行
A common implementation of a heap is the binary heap, in which the tree is a binary tree
这里的first heap是指优先队列，binary heap是指heap，简称heap是数据结构
从今以后，当您看到堆（在 ADT 的上下文中）时，它实际上意味着优先级队列 ADT，并且堆是 it.hence 的实现。堆是一个 DS。
还有你引用的地方：
" heap is a specialized tree-based data structure"
这只是意味着它是一个 DS 而不是 ADT。
1) Java 软件结构，国际版 [John Lewis, Joseph Chase]
An abstract data type (ADT) is a data type whose values and operations
are not inherently defined within a programming language. It is
abstract only in that the details of its implementation must be
defined and should be hidden from the user. A collection, therefore,
is an abstract data type.
2) 算法，第 4 版，作者 Robert Sedgewick 和 Kevin Wayne
Using abstract data types You do not need to know how a data type is implemented in order to be able to use it.
因此，如果您只设计这样的行为：
3) Wikipead 堆操作：
Basic
find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
insert: adding a new key to the heap (a.k.a., push[4])
extract-max (or extract-min): returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap (a.k.a., pop[5])
delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.[6]
Creation
create-heap: create an empty heap
heapify: create a heap out of given array of elements
merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps.
meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
Inspection
size: return the number of items in the heap.
is-empty: return true if the heap is empty, false otherwise.
Internal
increase-key or decrease-key: updating a key within a max- or min-heap, respectively
delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap)
sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.
sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.
真的这只是一个ADT，实现的是Data Structure，其实两本书中有一本把堆定义为ADT
因此，通过 1 和 2，表明 3 可以是堆的 ADT，因为您可以使用数组和指针等实现堆。和优先队列一样，但是时间复杂度可以改变
在 Java Software Structures,International Edition [John Lewis, Joseph Chase] 中有 HeapADT
public interface HeapADT<T> extends BinaryTreeADT<T>
{
/**
* Adds the specified object to this heap.
*
* @param obj the element to be added to this heap
*/
public void addElement (T obj);
/**
* Removes element with the lowest value from this heap.
*
* @return the element with the lowest value from this heap
*/
public T removeMin();
/**
* Returns a reference to the element with the lowest value in
* this heap.
*
* @return a reference to the element with the lowest value in this heap
*/
public T findMin();
}
但在 算法中，罗伯特·塞奇威克和凯文·韦恩的第 4 版 将 PriorityQueue 作为 ADT：
public class MaxPQ< Key extends Comparable<Key>>
MaxPQ() create a priority
queueMaxPQ(int max) create a priority queue of initial capacity max
MaxPQ(Key[] a) create a priority queue from the keys in a[]
void insert(Key v) insert a key into the priority queueKey
max() return the largest keyKey
delMax() return and remove the largest key
boolean isEmpty() is the priority queue empty?
int size() number of keys in the priority queue
作为 DS：https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
而且我认为他们只会这样说：
The binary heap is a data structure that can efficiently support the
basic priority-queue operations. In a binary heap, the keys
因为他们在谈论实现：
are stored in an array such that each key is guaranteed to be
larger than (or equal to) the keys at two other specific positions.
另一个例子可以说，关于 List，List 可以是一个 adt，静态数组和动态数组是实现 List 的数据结构，但是另一个作者将 ADT 定义为，因为这是预期的行为。
您可以在另一本书中查看此数组：N. S. KUTTI、P. Y. PADHYE 的《C++ 中的数据结构》（您可以查看 here）
最后，如果您要定义某物的行为，我会说它是 ADT，如果您正在执行实现，我会说它是 DS。
编辑：
书籍之间的又一个矛盾
Java Robert Lafore
中的数据结构和算法
A priority queue is a more specialized data structure
我正在上数据结构课程，对什么被认为是 ADT（抽象数据类型）而什么不是（如果不是 ADT，那么它一定是实施？）。
具体来说，我说的是堆。
我在维基百科上读到“堆是一种专门的基于树的数据结构”这是否意味着它是一个 ADT？如果是这样，那么我无法理解同样来自维基百科的以下行 "The heap is one maximally efficient implementation of an abstract data type called a priority queue".
我的意思是，Heap 可以是一个 ADT 还是其他一些 ADT 的实现（在这种情况下是优先队列的实现？我理解 ADT 的概念，在二叉堆的上下文中我理解它可以使用数组实现，其中 arr[i] 是 arr[2i] 和 arr[2i + 1] 的父级
我只是对堆是否可以一方面是使用数组实现的 ADT 而另一方面是实现其他 ADT 的数据结构感到困惑。
想得到一些关于这个的澄清。
堆不被视为抽象数据类型。
堆是一种特殊的基于树的数据结构，它是称为优先队列的抽象数据类型的实现。
堆不是 ADT。它是一个数据结构。
强制性维基百科引用：
In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.
奖励内容灵感来自 Steve McConnell 的代码完成 - 2。
数据结构是低级实现域项，与在问题域中工作的 ADT 形成对比。 ADT 让您可以操纵真实世界的实体，而不是低级的实现实体。您可以将单元格添加到电子表格、window 到 window 类型的新类型或火车上的另一位乘客，而不是将节点插入链表或将项目添加到堆模拟.
可以清楚的看到heap定义了insert(), heapify(), peek(), getTop()等语义——列在here细节。因此它是一个数据结构。
但是，如果您模拟俄罗斯方块游戏，其中添加一个新方块会简单地移动并坐在它掉落的任何地方的顶部，这个俄罗斯方块游戏的 UI 将实际上是一个ADT。
我会尝试以相反的方式澄清这种混淆。引用来自 here 的维基百科：
While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
因此堆只是优先级队列抽象数据类型 (ADT) 的一种实现，它可以在下面列出的许多其他类型中实现，但可能不限于：
- 无序数组
- 无序列表
- 有序数组
- 有序列表
- 二叉搜索树 (BST)
- 平衡二叉搜索树（AVL 树）
- 二叉堆（OP询问）
优先队列ADT中主要操作的堆实现与其他可能实现的时间效率比较：
----------------------------------------------------------------------------
| Implementation | Insertion | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1 | n | n
----------------------------------------------------------------------------
| Unordered List | 1 | n | n
----------------------------------------------------------------------------
| Ordered Array | n | 1 | 1
----------------------------------------------------------------------------
| Ordered List | n | 1 | 1
----------------------------------------------------------------------------
| BST | logn (avg.) | logn (avg.) | logn (avg.)
----------------------------------------------------------------------------
| Balanced BST | log n | log n | log n
----------------------------------------------------------------------------
| Binary Heaps | log n | log n | 1
我向您展示的是来自维基百科的完整行，而您只引用了混淆的行的一部分 you.maybe 如果您只读到行的下一部分，您会更好地理解它。
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. A common implementation of a heap is the binary heap, in which the tree is a binary tree
这里说
in fact priority queues are often referred to as "heaps", regardless of how they may be implemented.
由于堆数据结构（DS）的流行，在实现优先级队列时ADT.priority队列ADT通常被称为堆
在维基百科引用的下一行
A common implementation of a heap is the binary heap, in which the tree is a binary tree
这里的first heap是指优先队列，binary heap是指heap，简称heap是数据结构
从今以后，当您看到堆（在 ADT 的上下文中）时，它实际上意味着优先级队列 ADT，并且堆是 it.hence 的实现。堆是一个 DS。
还有你引用的地方：
" heap is a specialized tree-based data structure"
这只是意味着它是一个 DS 而不是 ADT。
1) Java 软件结构，国际版 [John Lewis, Joseph Chase]
An abstract data type (ADT) is a data type whose values and operations are not inherently defined within a programming language. It is abstract only in that the details of its implementation must be defined and should be hidden from the user. A collection, therefore, is an abstract data type.
2) 算法，第 4 版，作者 Robert Sedgewick 和 Kevin Wayne
Using abstract data types You do not need to know how a data type is implemented in order to be able to use it.
因此，如果您只设计这样的行为：
3) Wikipead 堆操作：
Basic
find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
insert: adding a new key to the heap (a.k.a., push[4])
extract-max (or extract-min): returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap (a.k.a., pop[5])
delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.[6]
Creation
create-heap: create an empty heap
heapify: create a heap out of given array of elements
merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps.
meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
Inspection
size: return the number of items in the heap.
is-empty: return true if the heap is empty, false otherwise.
Internal
increase-key or decrease-key: updating a key within a max- or min-heap, respectively
delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap)
sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.
sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.
真的这只是一个ADT，实现的是Data Structure，其实两本书中有一本把堆定义为ADT
因此，通过 1 和 2，表明 3 可以是堆的 ADT，因为您可以使用数组和指针等实现堆。和优先队列一样，但是时间复杂度可以改变
在 Java Software Structures,International Edition [John Lewis, Joseph Chase] 中有 HeapADT
public interface HeapADT<T> extends BinaryTreeADT<T>
{
/**
* Adds the specified object to this heap.
*
* @param obj the element to be added to this heap
*/
public void addElement (T obj);
/**
* Removes element with the lowest value from this heap.
*
* @return the element with the lowest value from this heap
*/
public T removeMin();
/**
* Returns a reference to the element with the lowest value in
* this heap.
*
* @return a reference to the element with the lowest value in this heap
*/
public T findMin();
}
但在 算法中，罗伯特·塞奇威克和凯文·韦恩的第 4 版 将 PriorityQueue 作为 ADT：
public class MaxPQ< Key extends Comparable<Key>>
MaxPQ() create a priority
queueMaxPQ(int max) create a priority queue of initial capacity max
MaxPQ(Key[] a) create a priority queue from the keys in a[]
void insert(Key v) insert a key into the priority queueKey
max() return the largest keyKey
delMax() return and remove the largest key
boolean isEmpty() is the priority queue empty?
int size() number of keys in the priority queue
作为 DS：https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
而且我认为他们只会这样说：
The binary heap is a data structure that can efficiently support the basic priority-queue operations. In a binary heap, the keys
因为他们在谈论实现：
are stored in an array such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions.
另一个例子可以说，关于 List，List 可以是一个 adt，静态数组和动态数组是实现 List 的数据结构，但是另一个作者将 ADT 定义为，因为这是预期的行为。
您可以在另一本书中查看此数组：N. S. KUTTI、P. Y. PADHYE 的《C++ 中的数据结构》（您可以查看 here）
最后，如果您要定义某物的行为，我会说它是 ADT，如果您正在执行实现，我会说它是 DS。
编辑：
书籍之间的又一个矛盾
Java Robert Lafore
中的数据结构和算法A priority queue is a more specialized data structure