Underlying DataStructure of Java PriorityQueue

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.

Because the PriorityQueue is just a Queue with the Heapify technique to guarantee good performance during insertion/deletion.

Heap means Heapify technique

Why PriorityQueue uses the Heapify technique?

• Heapifying is a method for inserting/deleting with the worst case of O(log₂ N)

What is the inheritance hierarchy of PriorityQueue?

public class PriorityQueue<E> extends AbstractQueue<E> {}

public abstract class AbstractQueue<E> extends AbstractCollection<E> {}

public abstract class AbstractCollection<E> implements Collection<E> {}

What is the inheritance hierarchy of List?

public interface List<E> extends Collection<E> {}

Why the PriorityQueue does not extend the List interface?

Because the List interface provides operations not defined or needed to the PriroityQueue like get(index), and the implementation just add() and poll() which similar to the queue mechanism which is insertion to the tail and poll from the head, and not sequential insertion like ArrayList or LinkedList which are extending the List interface. And no ability to get the values with index position.

What is the difference between PriorityQueue and Queue?

PriorityQueue uses the "Heapify" technique and can be Min PQ or Max PQ and you can simply define that when you declare the constructor of the PriorityQueue, while the Queue just adds the values to the tail and poll from the head.

What are the benefits to use PriorityQueue?

The big benefit is you can define Min PQ or Max PQ and get the elements in sorting order ascending or descending with time complexity O(log₂ N), and this important for many applications like finding the shortest path, collision of particles detection, etc.