Priority Queue | Introduction

05 min read

Priority Queue is an extension of queue with the following properties.
1) Every item has a priority associated with it.
2) An element with high priority is dequeued before an element with low priority.
3) If two elements have the same priority, they are served according to their order in the queue.

A typical priority queue supports the following operations.
1) insert(item, priority): Inserts an item with given priority.
2) getHighestPriority(): Returns the highest priority item.
3) deleteHighestPriority(): Removes the highest priority item.

Steps for array implementation of priority queue : A simple implementation is to use array of following structure.

struct item {
   int item;
   int priority;
}

  • insert() operation can be implemented by adding an item at end of array in O(1) time.

  • getHighestPriority() operation can be implemented by linearly searching the highest priority item in array. The time complexiy of this operation is O(n).

  • deleteHighestPriority() operation can be implemented by first linearly searching an item and then removing the item by moving all subsequent items one position back.We can also use Linked List, time complexity of all operations with linked list remains same as array. The advantage with linked list is deleteHighestPriority() can be more efficient as we don’t have to move items.

Implementation of priority queue using Heaps:


Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time. With Fibonacci heap, insert() and getHighestPriority() can be implemented in O(1) amortized time and deleteHighestPriority() can be implemented in O(Logn) amortized time.

Applications of Priority Queue:


1) CPU Scheduling
2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
3) All queue applications where priority is involved.

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error