Priority Queues

From Embedded Systems Learning Academy
Jump to: navigation, search

What are priority Queues?

A priority queue is essentially a list of items in which each item has associated with it a priority. Items are inserted into a priority queue in any, arbitrary order. However, items can be retrieved based on priority.Priority queues are often used in the implementation of algorithms.While priority queues are often implemented with heaps, they are conceptually distinct from heaps.

A typical priority queue supports following operations.

  • Insert(item, priority): Inserts an item with given priority.
  • GetHighestPriority()  : gets the highest priority item.
    /* Below is the basic info in priority queue data structure */
    struct node
        int priority;
        int var;
        struct node *next;

    /* Pseudo code to Insert the priority element in the queue */

    void insert(int value,  int priority)
       priorityEle->var= value;
       priorityEle->priority = priority;
       /* Insert this element in the queue */   

    void GetHighestPriority()
       int max = 0;
       max = start->priority;

       /* Check the max value with priority element of next element in queue */     
       while(start->next != NULL)
          Store start->next in start
          if( max < start->priority)
             max = start->priority;

Priority Queue Applications:

  • Event driven simulation
  • Data compression etc