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.
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.