堆是否被视为抽象数据类型?

堆不是ADT。它是一个数据结构。

维基百科必须引用:

在计算机科学中,抽象数据类型(ADT)是一种数学 数据类型的模型,其中数据类型由其行为定义 就可能的值而言,对此类数据的可能操作, 以及这些操作的行为。这与数据形成对比 结构,它们是数据的具体表示,是 实现者的观点,而不是用户的观点。

奖励内容的灵感来自Steve McConnell的Code Complete-2。

• 您可以清楚地看到堆定义了诸如insert()、heapify()、peek()、getTop()等语义-列出 here 详细地因此,它是一种数据结构。

• 然而,如果你模拟一个俄罗斯方块游戏,在游戏中添加一个新的方块会简单地放在它落下的地方,那么这个俄罗斯方块的UI实际上就是一个ADT。

我会试图用另一种方式澄清这种困惑。引用维基百科 here :

虽然优先级队列通常使用堆实现,但它们是 在概念上与堆不同。优先级队列是抽象的 “列表”或“地图”等概念;就像可以实现列表一样 通过链表或数组,可以实现优先级队列

因此堆只是优先级队列抽象数据类型(ADT)的一种实现,可以在下面列出的许多其他类型中实现,但可能不限于:

• 无序阵列
• 无序列表
• 有序阵列
• 有序列表
• 二进制搜索树(BST)
• 二进制堆(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

堆不被视为抽象数据类型。

堆是一种专门的基于树的数据结构,它是称为优先级队列的抽象数据类型的实现。

看见 https://en.wikipedia.org/wiki/Heap_(data_structure)

我给你看维基百科上的完整一行,而你只引用了那一行中让你困惑的部分。如果你只走到下一段,也许你会更好地理解它。

堆是称为优先级队列的抽象数据类型的一种最高效的实现,事实上,优先级队列通常被称为“堆”,无论它们如何实现。堆的一个常见实现是二进制堆,其中的树是二进制树

这里写着

事实上,优先级队列通常被称为“堆”,无论它们如何实现。

由于堆数据结构(DS)的流行,在实现优先级队列ADT时。优先级队列ADT通常称为堆

在维基百科引用的下一行

堆的一个常见实现是二进制堆,其中的树是二进制树

这里,第一堆表示优先级队列,而短堆中的二进制堆表示数据结构。

也可以引用以下内容:

“堆是一种特殊的基于树的数据结构”

这仅仅意味着它是一个DS而不是ADT。

1) Java软件结构,国际版[John Lewis,Joseph Chase]

抽象数据类型(ADT)是其值和操作的数据类型 不是在编程语言中固有定义的。它是 只有在其实现的细节必须是 定义并对用户隐藏。因此,收藏, 是抽象数据类型。

2) 算法,第4版,Robert Sedgewick和Kevin Wayne

使用抽象数据类型为了能够使用它,您不需要知道数据类型是如何实现的。

因此,如果你只是在设计这样的行为:

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,实现是数据结构,事实上,两本书中的一本将堆定义为ADT

因此,通过1和2表示3可以是堆的ADT,因为您可以使用数组和指针等实现堆。优先级队列也是如此,但时间复杂性可能会改变

在 Java软件结构,国际版[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版,Robert Sedgewick和Kevin Wayne 将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

我认为他们只会这样说:

这个 二进制堆是一种数据结构

因为他们谈论的是实施:

是 存储在数组中 确保每个密钥 大于(或等于)其他两个特定位置的键。

另一个例子可以说,关于List,List可以是一个adt,静态数组和dinamic数组是实现List的数据结构,但另一个作者将adt定义为,因为这是预期的行为。

您可以在另一本书中查看此数组: here )

最后,如果你定义了某个东西的行为,我会说这是一个ADT,如果你正在执行这个实现,我会称它是一个DS。

编辑:

书籍之间的另一个矛盾

数据结构;Java中的算法Robert Lafore

优先级队列是一种更专用的数据结构