Priority queues.


What is a priority queue?

A priority queue is a data structure where each node has a priority. The priority queue is as same as a normal queue except that every node has a priority associated with it.The priority plays the key role while processing the nodes. In other words, while processing the nodes, nodes with higher priority gets the first chance .  If multiple nodes have the same priority, then the processing can be done as per our application requirement such as processing in the order of inserting.

Firstly, to understand it better imagine a doctor is visiting the patients in a hospital. The doctor will be checking the patients in the order of severity of the patients’ condition. While examining a patient, Immediately a patient arrived who just met with an accident and in critical condition. So examining all other patients are kept aside and the doctor will check the patient who met with an accident right away. This exactly how a priority queue works.

Meanwhile, if you are not aware of the queue data structure read my blog post about them here

Some of the examples of the priority queue are:-

Implementing priority queue with singly linked list:-

A priority queue can be easily implemented using a singly linked list. Singly-linked list‘s insertion process can be used for implementing a priority queue. The pseudocode will also be the same. It’s just that we compare the priority of the current insertion node with the next node and thus placing the node at an appropriate position.

Priority queue.

 

Implementing priority queues with binary heap:-

In the priority queue, storing of the data based upon priority of the data. This is similar to the max or min binary heap. A max binary heap every node is grater than child nodes, whereas in the case of min binary heap every root node is smaller than the child nodes. So without any change in the implementation, we can use a max or min binary heap as a priority queue. But instead of storing the nodes by comparing the values, we have to store them based on the priority. 

Meanwhile, if you want to know more about the heaps please do read it from my blog here. 
The implementation is as shown below.

class Node {
    int value;
    int priority;
    Node(int value, int priority) {
        super();
        this.value = value;
        this.priority = priority;
    }
}

class PriorityQueueWithHeaps {
    ArrayList<Node> values;
    public PriorityQueueWithHeaps() {
        super();
        this.values = new ArrayList<>();
    }
    public void enQueue(Integer value, int priority) {
        Node newNode = new Node(value, priority);
        this.values.add(newNode);
        this.bubbleUp();
    }
    public void bubbleUp() {
        int index = this.values.size() - 1;
        Node element = this.values.get(index);
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            Node parent = this.values.get(parentIndex);
            if (element.priority > parent.priority) {
                this.values.set(parentIndex, element);
                this.values.set(index, parent);
                index = parentIndex;
            }
            else {
                break;
            }
        }
    }
    public int deQueue() {
        Node max = this.values.get(0);
        Node end = this.values.get(this.values.size() - 1);
        if (this.values.size() > 0) {
            this.values.set(0, end);
            this.bubbleDown(0);
        }
        return max.value;
    }
    public void bubbleDown(int bubbleDownFromIndex) {
        int index = bubbleDownFromIndex;
        int length = this.values.size();
        Node element = this.values.get(index);
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            Node leftChild = null, rightChild = null;
            Integer swap = null;
            if (leftChildIndex < length) {
                leftChild = this.values.get(leftChildIndex);
                if (leftChild.priority > element.priority) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.values.get(rightChildIndex);
                if (
                    (swap == null && rightChild.priority > element.priority) ||
                    (swap != null && rightChild.priority > leftChild.priority)) {
                    swap = rightChildIndex;
                }
            }
            if (swap == nullbreak;
            this.values.set(index, this.values.get(swap));
            this.values.set(swap, element);
            index = swap;
        }
        this.values.remove(length - 1);
    }
}
class Node {
    constructor(value, priority) {
        this.value = value;
        this.priority = priority;
    }
}
class MaxBinaryHeap {
    constructor() {
        this.values = [];
    }
    enqueue(value, priority) {
        let newNode = new Node(value, priority);
        this.values.push(element);
        this.bubbleUp();
    }
    bubbleUp() {
        let index = this.values.length - 1;
        const element = this.values[index];
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            let parent = this.values[parentIndex];
            if (element.priority > parent.priority) {
                this.values[parentIndex] = element;
                this.values[index] = parent;
                index = parentIndex;
            }
            else {
                break;
            }
        }
    }
    dequeue() {
        var max = this.values[0];
        var end = this.values.pop();
        if (this.values.length > 0) {
            this.values[0] = end;
            this.bubbleDown(0);
        }
        return max;
    }
    bubbleDown(bubbleDownFromIndex) {
        var index = bubbleDownFromIndex;
        const length = this.values.length;
        const element = this.values[index];
        while (true) {
            var leftChildIndex = 2 * index + 1;
            var rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;
            if (leftChildIndex < length) {
                leftChild = this.values[leftChildIndex];
                if (leftChild.priority > element.priority) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.values[rightChildIndex];
                rightChild = this.values[rightChildIndex];
                if (
                    (swap === null && rightChild.priority > element.priority) ||
                    (swap !== null && rightChild.priority > leftChild.priority)) {
                    swap = rightChildIndex;
                }
            }
            if (swap === nullbreak;
            this.values[index] = this.values[swap];
            this.values[swap] = element;
            index = swap;
        }
    }
}

Applications of the priority queue:-

Some of the real life examples of the priority queue are

  • Allocating memory and processors for threads in multi threading process.
  • CPU scheduling.
  • data transfer between the IO buffers, etc.