Priority queue is a data structure that extends the queue data structure with a priority dimension. **Queue** is a list of elements taken in the same order as they arrived. For instance, a line of people waiting to pay at the Supermarket behaves like a queue: first-in, first-served, or FIFO (first in, first out).

**Priority queue** adds a priority to each element’s value. If we go back to the example of a line of people in a supermarket. You can add preferred lanes, for example, Seniors (65+ years old) and pregnant women. If you have Seniors in the line, you will take them first, even if other people arrived before them. That’s what a priority queue (PQ) does. If all elements in a PQ have the same priority, then it will behave like a regular queue.

There are many real-world applications for priority queues, such as:

- System to triage hospital patients and attend them by their severity order.
- Forward network packages in order of urgency (e.g., “real-time video call” should go before “time sync checks,” so to speak)
- Scheduling tasks in a system: “critical” goes before “shadow drawing” for instance.
- Asynchronous control flows like firing events (or notifying observers) in a certain order.
- Keeping track of top k elements efficiently
- Keeping track of median numbers in constant time
- Used in some graph algorithms like Dijkstra for finding the shortest path between two points. The distance among points is used as a priority.

- Let’s explore several possibilities for data structures we could use to implement a priority queue:
- Unordered array
A simple, yet inefficient implementation, as retrieving the max element would require searching the entire array.

- Sorted array
This is not a very efficient implementation either. Inserting a new element requires linearly searching the array for the correct position. Removing similarly requires a linear time: the rest of the elements need to be adjusted (shifted) into correct positions.

- Hash table
Although inserting into a hash table takes constant time (given a good hash function), finding the max element takes linear time. Therefore, this would be a poor choice for the underlying data structure.

- Heap
It turns out that that a heap makes an efficient priority queue.

- Unordered array

Operation | Unordered array | Sorted array | Hash table | Binary heap |
---|---|---|---|---|

insert |
$Θ(1)$ |
$Θ(N)$ |
$Θ(1)$ |
$Θ(log(N))$ |

maxElement |
$Θ(N)$ |
$Θ(1)$ |
$Θ(N)$ |
$Θ(1)$ |

removeMaxElement |
$Θ(N)$ |
$Θ(1)$ |
$Θ(N)$ |
$Θ(log(N))$ |

public class MyPriorityQueueWithArray { private int count = 0; private int capacity = 10; private PriorityNode[] elements = new PriorityNode[capacity]; public void enqueue(PriorityNode node) { if (node == null || node.getData() == null) { return; } System.out.println("node: " + node.toString()); System.out.println("count: " + count); int position = 0; if (count == 0) { /** * tail has the highest priority */ elements[position] = node; } else { PriorityNode highestNode = elements[position]; while (highestNode != null && node.getPriority() <= highestNode.getPriority()) { position++; highestNode = elements[position]; } add(node, position); } System.out.println("insert position: " + position); System.out.println("\n"); count++; } private void add(PriorityNode node, int position) { if (count == capacity) { /* * when full, double its size */ capacity = capacity * 2; } PriorityNode[] temp = new PriorityNode[capacity]; int index = 0; int lastIndex = count + 1; while (index < lastIndex) { if (index < position) { /** * front */ temp[index] = elements[index]; } else if (index == position) { /** * middle */ temp[position] = node; } else { /** * back */ temp[index] = elements[index - 1]; } index++; } elements = temp; } public PriorityNode removeAt(int position) { PriorityNode[] temp = new PriorityNode[capacity]; PriorityNode removedNode = elements[position]; int index = 0; int lastIndex = count + 1; while (index < lastIndex) { if (index < position) { /** * front */ System.out.println("front"); temp[index] = elements[index]; } else if (index == position) { /** * middle */ System.out.println("middle"); } else { /** * back */ System.out.println("back"); temp[index - 1] = elements[index]; } if (temp[index] != null) System.out.println("temp: " + temp[index].toString()); index++; System.out.println("\n"); } elements = temp; return removedNode; } /** * Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty. */ public PriorityNode peek() { return elements[0]; } /** * Retrieves and removes the head of this queue, or returns null if this queue is empty. */ public PriorityNode dequeue() { return removeAt(0); } public void print() { int index = 0; PriorityNode node = elements[0]; while (node != null && count > index) { System.out.println((index + 1) + ". " + node.toString()); index++; node = elements[index]; } } }