It seems to me that a tree or a heap is a concept and not a concrete implementation of some other abstract data structure.

For example a heap can be implemented with a table. Then why it is not considered abstract?

  • $\begingroup$ It is rather opinionated to say "a tree is a concrete data structure". "In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, ...", says Wikipedia. $\endgroup$ – John L. Apr 7 '19 at 0:11

An abstract data type (ADT) is an interface: it describes the operations that can be performed and what their externally visible behavior should be. There are typically many possible ways to implement that interface.

A data structure is an implementation of such an interface: it provides code or fully specifies the internal behavior.

A binary search tree is not an ADT; it specifies more than a list of supported operations (like insert, find) but also how they can be implemented (by a particular data structure in the shape of a tree). A heap is not an ADT; it specifies more than a list of supported operations (extract-min, insert), but also how those operations should be implemented (by storing the elements in an array in a particular way and manipulating them in a specific fashion).

See also https://en.wikipedia.org/wiki/Abstract_data_type.

  • $\begingroup$ Nice answer. However, I beg to differ for the case of heap. For example, is heap an ADT or data structure that "provides code or fully specifies the internal behavior"? It depends strongly on the situation. It does not make much sense to say "let us create a heap from 1,2, 3, 4". Why? Because there are many kinds of heaps. A heap in general does NOT provide code or fully specifies the internal behavior. The situation can be explained more clearly by the classes in Java. $\endgroup$ – John L. Apr 6 '19 at 23:39
  • $\begingroup$ What I mean is, this answer might be good enough for beginners. However, it is not the full truth. $\endgroup$ – John L. Apr 6 '19 at 23:42
  • $\begingroup$ @Apass.Jack, Perhaps it depends what is meant by the word "heap". To me, in the absence of any indication to the contrary, that means the classic data structure for storing a binary heap in an array and updating it using the standard operations. If that's not what is meant by "heap" in this conversation, then my comments might not apply. $\endgroup$ – D.W. Apr 6 '19 at 23:42
  • $\begingroup$ Agreed that this case of heap depends on what is the meaning of heap. This answer might be good enough for a beginner, for whom heap could be equated to one specific implementation of the abstract heap. However, as you are aware, there are many kinds of heaps with different behaviors. $\endgroup$ – John L. Apr 6 '19 at 23:56
  • $\begingroup$ I noticed that you avoided/skipped the case of tree. I would prefer to say "tree is an ADT" to "tree is a concrete date type" in general. It is nice that you avoid to discuss "tree", this more general term. It is nice that this answer just discusses binary search tree, a clear-cut example to demonstrate the concepts without entailing another debate/discussion about "tree". $\endgroup$ – John L. Apr 7 '19 at 0:02

A concrete data type is absolutely defined. only certain inputs and outputs can exist in this.

Stacks, queues and heaps are abstract datatypes. They are just ideas, i.e. "black boxes" with a defined behavior. To implement them, you have to choose a suitable concrete datatype.; Abstract Data types can be constructed from known - or unknown data.

Now, Binary Trees are one of the most important data structures in computer science. We can think of a tree both as a mathematical abstraction and as a very concrete data structure used to efficiently implement other abstractions such as sets and dictionaries.

For example, to implement heap or AVL, we make use of a binary tree which makes tree as concrete data structure and heap as the ADT.

  • $\begingroup$ Stacks and queues can be viewed as ADTs, but I don't think "heap" is an abstract data type. A priority queue is an ADT; a heap is one way of implementing a priority queue (there are others). $\endgroup$ – D.W. Apr 7 '19 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.