CODEWITHSUNDEEP
javacollectionsqueueheappriority-queue
T.M15
T.M15

Reputation: 416

Underlying DataStructure of Java PriorityQueue

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?

Upvotes: 3

Views: 1900

Answers (2)

0xh3xa
0xh3xa

Reputation: 4859

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(log2 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(log2 N), and this important for many applications like finding the shortest path, collision of particles detection, etc.

Upvotes: 2

Monsieur Merso
Monsieur Merso

Reputation: 2106

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.

Upvotes: 2

Related Questions