Priority Queue

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.

Applications of Priority 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.

Implementations

  • 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.

Operation Unordered array Sorted array Hash table Binary heap

insert

maxElement

removeMaxElement

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];
        }
    }
}

 

Source code on Github

 

 

 




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published.