Menu
I'm taking Data-Structure course and got a little confused about what is considered to be an ADT (Abstract Data Type) and what isn't (and if it isn't an ADT then it must be the implementation?).
Specifically, I'm talking about Heap.
I've read in Wikipedia that " heap is a specialized tree-based data structure" does that mean it is an ADT? if so, then I can't understand the following line, also from Wikipedia "The heap is one maximally efficient implementation of an abstract data type called a priority queue".
I mean, can Heap be an ADT and also be an implementation of some other ADT (in this case an implementation of priority queue? I understand the concept of ADT and in the context of Binary Heap I understand that it can be implemented using array where arr[i] is the parent of arr[2i] and arr[2i + 1]
I'm just confused about whether a Heap can be in one hand an ADT which implemented using array and on the other hand a data-structure that implements other ADT.
Would like to get some clarifications about this.
756
In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
Heap is a very useful data structure with many applications (e.g Heapsort and Priority Queues (ADT)). Heap elements are typically allocated as a dynamic array. However, the elements are conceptually forming a complete tree.
Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented.
The array is a basic abstract data type that holds an ordered collection of items accessible by an integer index.
Abstract Data Types are focused on what, not how (they're framed declaratively, and do not specify algorithms or data structures). Common examples include lists, stacks, sets, etc. ADTs provide a way for us to formally define reusable modules in a way that is mathematically sound, precise, and unambiguous.
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes.
Heap is not an ADT. It is a Data Structure.
The obligatory Wikipedia quote:
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.
Bonus content inspired from Code Complete - 2 by Steve McConnell.
Data Structures are low-level implementation domain items, in contrast with ADTs which work in the problem domain. ADTs let you manipulate real-world entities rather than low-level, implementation entities. Instead of inserting a node into a linked-list or adding an item to a heap, you can add a cell to a spreadsheet, a new type of window to window types, or another passenger to a train simulation.
You can clearly see that heap has defined semantics like insert(), heapify(), peek(), getTop() etc. - listed here in detail. Hence it is a data structure.
However, if you simulate a game of Tetris where adding a new block will simply go and sit on top of wherever it falls, this Tetris game's UI will actually be an ADT.
118
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
