Underlying DataStructure of Java PriorityQueue

Question

Referencing from the book Java: The Complete Reference, "Queue" interface extend "Collection" interface. Also, "PriorityQueue" extends "AbstractQueue" class and implements "Queue" interface.

Also, as per lots of articles over Internet, Heaps provides the most efficient Priority Queue implementation considering both Insert and Remove in O(logn). And being complete binary tree, heaps can be implemented simply on an array/list.

My question is, If heaps are efficient for Priority Queues, than why PriorityQueue uses a Queue interface? Why it's not using List interface? Otherwise, what is the underlying concept/idea of the implementation, providing time complexity same(or better) as heaps?

Answer 1

Interfaces are "contracts" which ensure that classes implementing them will provide certain "behavior" - methods.

So client code (code that will make use of PriorityQueue for example) will have guarantees that this class will have behavior that may be expected only from Queue implementation.

In other words:

List interface has methods that are useful to work with lists.

Queue interface has methods that are useful for work with queues.

PriorityQueue that implements methods of a List interface just won't be comfortable to work with.

And vice versa, imagine ArrayList that implements Queue interface - it will be chaos to work with such thing.

More related to your question: There may be multiple implementations of Queue interface - on array, on ArrayList or LinkedList with different time complexity and so on, but all of them will provide same set of methods of Queue interface.