CODEWITHSUNDEEP
javascriptjavadata-structuresadt
Jonas Grønbek
Jonas Grønbek

Reputation: 2019

Are Heap and Priority Queue, data structures or abstract data types?

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?

Upvotes: 0

Views: 838

Answers (2)

IkhideIfidon
IkhideIfidon

Reputation: 23

If you ever need to use another data structure to implement your desired data structure, then your desired data structure is better described as ABSTRACT DATA STRUCTURE.

Some examples of ADT are:

  1. Stack
  2. Queue
  3. Deque
  4. Priority Queue
  5. Tree, etc

I hope this helps.

Upvotes: 0

vicpermir
vicpermir

Reputation: 3702

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.

Upvotes: 1

Related Questions