Noa*_*oam 10 heap priority-queue abstract-data-type data-structures
我正在学习数据结构课程并且对于被认为是ADT(抽象数据类型)和什么不是(如果它不是ADT那么它必须是实现？)有点困惑.
具体来说,我在谈论堆.
我在维基百科中读到"堆是一种专门的基于树的数据结构",这是否意味着它是一个ADT？如果是这样,那么我无法理解以下这一行,也来自维基百科"堆是一种称为优先级队列的抽象数据类型的最高效实现".
我的意思是,Heap可以是ADT还是其他ADT的实现(在这种情况下是优先级队列的实现？我理解ADT的概念并且在Binary Heap的上下文中我理解它可以使用数组实现arr[i]是的父arr[2i]和arr[2i + 1]
我只是混淆一个堆是否可以在一方面使用阵列实现的ADT和在另一方面一个数据结构实现其他ADT.
想得到一些澄清.
堆不是ADT.它是一种数据结构.
强制性的维基百科报价:
在计算机科学中,抽象数据类型(ADT)是数据类型的数学模型,其中数据类型是从数据用户的角度定义的行为(语义),特别是在可能的值方面,可能的对此类数据的操作,以及这些操作的行为.这与数据结构形成对比,数据结构是数据的具体表示,并且是实施者而非用户的观点.
奖金内容受到Steve McConnell的Code Complete -2的启发.
与在问题域中工作的ADT相比,数据结构是低级实现域项.ADT允许您操纵实际实体而不是低级实现实体.您可以将单元格添加到电子表格,将新类型的窗口添加到窗口类型,或将其他乘客添加到火车模拟中,而不是将节点插入链接列表或将项目添加到堆中.
您可以清楚地看到堆已经定义了语义,如insert(),heapify(),peek(),getTop()等 - 这里详细列出.因此它是一种数据结构.
但是,如果你模拟一个俄罗斯方块游戏,那么添加一个新区块只会放置在任何位置的顶部,这个俄罗斯方块游戏的UI实际上将是一个ADT.
我会尝试以其他方式澄清这种混乱。从这里引用维基百科：
虽然优先级队列通常使用堆来实现，但它们在概念上与堆不同。优先级队列是一个抽象概念，类似于“列表”或“映射”；正如列表可以用链表或数组来实现一样，优先级队列可以用堆或各种其他方法（例如无序数组）来实现。
因此，堆是一种名为优先级队列的抽象数据类型（ADT）的实现。这意味着堆是一种数据结构。优先级队列 ADT 可以通过下面列出的许多其他方式来实现，但不限于：
将优先级队列 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