03 Priority Queues

Queues are usually First-In, First-Out. Items are removed from the queue in the order that they are added. But what if we wanted to change that slightly and say that we always want to access the highest priority item.

Rather than removing the items in the order they were added, when we add an item we assign it a priority and when we go to remove the item the highest priority item is the one that is removed. So it is not going to be First-In, First Out. This case it depends on highest priority for example think of it as emergency room in hospital.

In Priority Queue it is always when we take an item off the queue we always want the highest item first.

So if the values in the nodes indicate the priority and of course they can, then a max-heap is an ideal data structure for this because the value with the highest priority is always the root of the heap. So when you remove the highest priority the root is removed.

That means that the next highest priority item is now the root and we can remove that at the constant time. If we were to add a new item into the heap that has a higher priority item will be at the root. So we can always get the highest priority item in constant time.

Priority queue is an abstract data type implemented in max-heap.

Common operations are: Insert with highest priority, remove with highest priority, Poll, Peek.

Java has the Priority Queue class.

package priorityQueueEx1;

import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		pq.add(25);
		pq.add(-22);
		pq.add(0);
		pq.add(35);
		pq.add(-52);
		pq.add(4250);
		
		System.out.println("Peek: "+pq.peek());
		System.out.println(pq.remove());
		System.out.println("Peek: "+pq.peek());
		
		//Poll
		System.out.println(pq.poll());
		System.out.println("Peek: "+pq.peek());
	}
}

Output:
Peek: -52
-52
Peek: -22
-22
Peek: 0