I have seen similar questions and read a lot of the answers. One would think that I would know it then, however some of the answers were contradictory and now I am more confused than when I started.
My quest started of as - what is the difference between a Heap and a Priority Queue. To where I learned that Heap was a data structure and Priority Queue was a abstract data type. But why?
So far I found this answer to be the best: Simply put, the relation between data structure and abstract data type is the same as the relation between algorithm and pseudo-code. The first is an idea, the second a formal description (abstract, inaccessible).
Some mention that ADT is a language dependent term. Since it describes “data types not included in the standard library”. So in Java or JS a Heap is not in the standard library, but previously I learned that heaps are a data structure and not an abstract data type?
Can someone clarify in general what a data structure and abstract data type is?
A Priority Queue is an abstract data type, it can be implemented in many different ways.
A Heap is a data structure, the way it stores data and how it works with it are both well defined.
Using a heap to implement a priority queue is a good idea because the way a heap operates on the data aligns very well with the way a priority queue works. If you check the documentation for java.util.PriorityQueue you will see the following comment:
An unbounded priority queue based on a priority heap
You could think of an ADT as a high level logical description (what it does) while a data structure defines exactly how the data is stored and manipulated (how it's done).
Could you implement a priority queue using some other data structure? of course, probably not as efficiently though.