# Priority Queue using Java

Saksham Gupta
Last Updated: May 13, 2022

## Introduction

While stacks have a last-in-first-out (LIFO mechanism) and queues have a first-in-first-out mechanism (FIFO), priority queues are somewhat different. Just by the name itself, a priority queue is just a queue — with the added extension of associating a “priority” to each item in the queue. Just like queues, priority queues also have a FIFO mechanism. But what does “priority” mean in this case? What does it mean to assign a “priority” to an item in the queue?

Generally, the element’s value is considered for assigning the priority, i.e., its magnitude. For example, the element whose magnitude is highest is considered to be the element with the highest priority. However, in other cases, we can also mark an element with the lowest value as the element with the highest priority. Priorities can also be set by our needs.

Thus we can classify them into two categories.

1. Min Priority Queue: Minimum element has the highest priority.
2. Max Priority Queue: Maximum element has the highest priority.

Now, this sounds very interesting but you must be thinking about how to implement it, the answer is a heap data structure. Heaps? What are they?

heap is a data structure based on trees where the root of the tree contains the element whose priority is the highest or the lowest. A heap is a complete binary tree, Another new word? Well, in a complete binary tree every node has two child nodes except the leaf nodes. This means all the leaf nodes should be at the same level and all other internal nodes should contain two child nodes each.

Source: TechieDelight

In the first image, all levels are filled and have two children except the leaf nodes, whereas if we look at the second image, some nodes don't have two children (node with value 3).

## Declaration of Priority Queue using Java

Now let’s talk about the declaration of priority queue using Java. We can use different constructors to declare our priority queue.

1. PriorityQueue(): Creates a PriorityQueue with the initial default capacity (11) that orders its elements according to their natural ordering.

2. PriorityQueue(Collection<E> c): Creates a PriorityQueue containing the elements in the specified collection.

3. PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

4. PriorityQueue(int initialCapacity, Comparator<E> comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

5. PriorityQueue(PriorityQueue<E> c): Creates a PriorityQueue containing the elements in the specified priority queue.

6. PriorityQueue(SortedSet<E> c): Creates a PriorityQueue containing the elements in the specified sorted set.

Here ‘E’ refers to the type of element(Integer, String, etc.).

Let's now see some frequently used methods that are used to perform operations on the Priority Queue.

## Frequently used PriorityQueue Methods

The add() method as the name suggests is used to add a element in the Priority Queue.

Time Complexity

O(log(N)), where ‘N’ is the number of elements in the priority queue.

Okay, now you have understood how to insert an element in the queue but how to access the topmost element?

We can do that easily by using the peek function. Let us understand it more by the following piece of code.

## peek()

The peek() method simply returns the topmost element present in the priority queue.

Output

Time Complexity

O(1)

What if I have to delete the topmost element?

To do that we can simply use the poll() function. Here is an example.

## poll()

The poll() method deletes the topmost element of the priority queue.

Output

Time Complexity

O(1)

## Other Methods

By now, you have understood the basic methods of the priority queue using java. Now let’s look at some other important methods that are provided in java.

• clear()

It is used to remove all the elements from the priority queue.

Output

Time Complexity

O(N), where ‘N’ is the number of elements in the priority queue.

• contains()

It is used to check if an element is present in the queue or not. If yes, it returns true, else returns false.

Output

Time Complexity

O(1)

• iterator()

It returns an iterator to iterate over the elements in the priority queue.

Output

• remove(obj)

It removes the obj from the priority queue, if present. If more than one obj is present, it will remove only one of them.

Output

Time Complexity

O(1)

If the element is not present in the queue then the compiler throws an exception.

• toArray()

It returns us an array containing all of the elements in the queue.

Output

## Key Takeaways

Now that you have mastered the basics of priority queue using Java and saw how we could use its inbuilt methods to perform different functions. It’s time to move ahead to CodeStudio and practice some famous interview problems on the priority queue. CodeStudio offers interesting interview experiences and blogs like this one. Till then, keep learning, and Happy Coding!

By:- Saksham Gupta