Priority Queues–An Introduction

“We saw queues in which the people who come first goes out of the queue first!!.. even rowdies and politicians must follow this rule!!.. But current system doesn’t work like that..!! if rowdies or politicians come, they get more priority and VIP status.. For this we use priority queues”

See also

http://analgorithmaday.blogspot.com/2011/02/queuean-introduction.html

Metaphor

  As I said in the above quote, we need assign priority to each and every element instead of having just one priority condition, FIFO. This is major reason for going to priority queues.

Concept

  As explained by many, Priority Queues are not necessarily need to be implemented using Binary Heaps. But priority queues used for real time applications need to be efficient and faster. Where in computer world priority queue is used? Schedulers!!

  All OS schedulers use priority queues to allot CPU. The process with higher priority get CPU most of the time just because of this priority queues. So to get more efficient queues, people tend to use heaps. But we will first understand implementation of priority queue using array.

The important concept to be understood in priority queue is that, at most cases it just holds the priority value corresponding to an object. So, the priority is mostly an integer value associated with an object. They call this value as “key”. This first time we learn about keys!!.. so be careful to understand this.

“key1” “key2” “key3”   ---> Priority Queue

  V           V         V

  Obj1    Obj2   Obj3  ---> real system objects

For the example of OS Scheduler, process priority is the key and process itself is the real system object. The implementation internals of a small scheduler will be discussed in coming sections..

But in this article we will see about how these key’s are prioritized. Mostly based on max or min value!! min value suits some applications, max value suits some..

Some more examples of priority queues: Any Scoring system, Outlook task priority system, even gmail priority inbox.

Code

#define MAXQSIZE 10

class PriorityQueue

{

    int arr[MAXQSIZE];

    int idx;

public:

    PriorityQueue()

    {

        idx = 0;

    }

    bool insert(int elem)

    {

        if(idx > MAXQSIZE-1)

            return false;

        arr[idx++] = elem;

        return true;

    }

    bool remove(int& elem)

    {

        int maxIndex = 0;

        if(idx < 0)

            return false;

        for(int i = 1; i <= idx; i++) {

            if(arr[i] > arr[maxIndex])

                maxIndex = i;

        }

        elem = arr[maxIndex];

        //since idx++ is done by insert

        arr[maxIndex] = arr[idx-1]; 

        idx -= 1;

        return true;

    }

};

void main()

{

    int A[] = { 5, 4, 3, 2, 20, 7, 10};

    PriorityQueue pq;

    for(int i=0; i<7;i++) {

        pq.insert(A[i]);

    }

    int val=0;

    pq.remove(val);

}

Important points

• The above is a very simple implementation of priority queue based on queue implementation
• There is no front or back since we take the max element in each remove function call. This creates the hole we need. This hole is reused.
• This is very very simple priority queue with basic operations. Priority Queue ADT requires some more operations.
• The remove operations takes O(n) and insert operation in O(1). But both needs be at constant time for a real time scheduler
• The above code is practically very bad!! consider this equal to bubble sort :)
• We can use binary heaps, which gives heap remove with O(1) since the max element is always in index 0 in a heap
• Even insert takes less time O(log n) in case we use max heap. This is the wonder of data structures altering the performance of algorithms ;). But note that reverse is not true. Not all performance can be achieved by just changing the data structure..