Priority Queue

A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority element is retrieved first. Following example demonstrates priority queue.

priorityQue

A priority queue must at least support the following operations:

  • insert_with_priority: add an element to the queue with an associated priority.
  • pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it.
    This is also known as “pop_element(Off)“, “get_maximum_element” or “get_front(most)_element“.

Implementation

/*
 * Node Declaration
 */
struct node
{
	int priority;
	int info;
	struct node *link;
};
/*
 * Class Priority Queue
 */
class Priority_Queue
{
    private:
        node *front;
    public:
        Priority_Queue()
        {
            front = NULL;
        }
        /*
         * Insert into Priority Queue
         */
        void insert(int item, int priority)
        {
            node *tmp, *q;
            tmp = new node;
            tmp->info = item;
            tmp->priority = priority;
            if (front == NULL || priority < front->priority)
            {
                tmp->link = front;
                front = tmp;
            }
            else
            {
                q = front;
                while (q->link != NULL && q->link->priority <= priority)                     
                     q=q->link;
                tmp->link = q->link;
                q->link = tmp;
            }
        }
        /*
         * Delete from Priority Queue
         */
        void del()
        {
            node *tmp;
            if(front == NULL)
                cout<<"Queue Underflow\n";
            else
            {
                tmp = front;
                cout<<"Deleted item is: "<info<<endl;                 
                front = front->link;
                free(tmp);
            }
        }
        /*
         * Print Priority Queue
         */
        void display()
        {
            node *ptr;
            ptr = front;
            if (front == NULL)
                cout<<"Queue is empty\n";
            else
            {	
                cout<<"Queue is :\n";
                cout<<"Priority       Item\n";
                while(ptr != NULL)
                {
                    cout<priority<<"                 "<info<<endl;                     
                    ptr = ptr->link;
                }
            }
        }
};

Applications

  • Bandwidth Management
  • Discrete Event Simulation
  • Dijkstra’s Algorithm
  • Huffman coding
  • Best-first search algorithm
  • ROAM Triangulation algorithms
  • Prims algorithm for minimum Spanning tree