Priority Queue

 

• A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion but supports removal of elements in order of priority, that is, the element with first priority can be removed at any time
  
• Other data structures like stacks, queues, lists and trees store elements at specific positions, which are often positions in a linear arrangement of the elements determined by the insertion and deletion operations performed
  
• The priority queue ADT stores elements according to their priorities, and exposes no notion of position to the user
  
• A priority queue has a mechanism to determine which item has the highest priority and provides access to the largest item in the queue at any given time
  

  
   

• A priority queue needs a comparison rule that will never contradict itself
  
• In order for a comparison rule to be robust in this way, it must define a total order relation, which is to say that the comparison rule is defined for every pair of keys and it must satisfy the following properties
  
  • Reflexive property – k <= k
    
  • Antisymmetric property – if k1 <= k2 and k2 <= k1, then k1 = k2
    
  • Transitive property- if k1 <= k2 and k2 <= k3, then k1 <= k3
    

  
   

• A priority queue is a collection of elements, called values, each having an associated key that is provided at the time the element is inserted
  
• A key-value pair inserted into a priority queue is called an entry of the priority queue
  
• The name priority queue comes from the fact that keys determine priority used to pick entries to be removed
  
• The two fundamental methods of a priority queue are as follows
  
  • insert (k, x) – insert a value x with key k
    
  • removeMin() – return and remove an entry with the smallest key