Priority Queue

A priority queue is an abstract, linear data structure which is a modification of a queue, by assigning priorities to each item.

A priority queue can be transformed into a stack if the priority of the elements inserted is monotonically increasing, and a queue if the priority is monotonically decreasing.#todo elaborate.

Definition §

• A variation of the normal queue ADT, where items are also given a priority/rank
• Priority queues can either be minimum or maximum:
  • Minimum Priority Queues sort elements with the lower priority first
  • Maximum Priority Queues sort elements with the higher priority first
• The same operations of the queue apply here, such as enqueue, dequeue, etc.

ADT Signature §

name: PQueue
import Element, Boolean; 
ops:
	new: → PQueue; 
	enqueue : PQueue × element x priority → PQueue; 
	dequeue : PQueue → PQueue x element; 
		dequeue_min : PQueue → PQueue x element; 
		dequeue_max : PQueue → PQueue x element; 
	peek : PQueue → elem; 
	isEmpty : Queue → Boolean;
	etc.

Sorting §

Priority queues can be used to implement different sorting algorithms depending on the concrete implementation. If we take the elements that need to be sorted, enqueue all of them with priority equal to the key we want to sort by and then dequeue all of them, we get back a sorted list.

• The unsorted array implementation follows the same principle as selection sort, since both follow the process of linear searching for the maximum element.
• The sorted array implementation is similar to insertion sort, since whenever we insert an element, we need to find the right position and shift elements.
• The heap implementation is like Heapsort.

Time Complexity §

Unsorted Array §

If an unsorted array is used to implement the priority queue, we would need to

Basic Operation: Array Access

Assumptions:

• $A$ = The underlying array used to store the priority queue
• $n$ = The number of elements in the priority queue

Operation	Worst Case (WC)	Average Case (AC)	Best Case (BC)	Case descriptions
Enqueue an element $x$ with priority $p$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Appending it to the end of the array (at $A[n]$) is constant time
Dequeue with minimum/maximum priority	$\Theta (n)$	$\Theta (n)$	$\Theta (1)$	Equivalent to linear searching for the element with min/max priority. See its time complexity here Swap it with the last element. Then remove the last element and reduce $n$ by 1

Sorted Array §

Assuming the array is sorted in reverse order for a minimum priority queue, and normal order for a maximum priority queue.

Operation	Worst Case (WC)	Average Case (AC)	Best Case (BC)	Case descriptions
Enqueue an element $x$ with priority $p$	$\Theta (n)$	$\Theta (n)$	$\Theta (n)$	Equivalent to linear searching for the element with min/max priority, then shifting remaining elements to the right. Both operations combined result in $\Theta (n)$ since whichever elements that weren’t searched through get shifted.
Dequeue with minimum/maximum priority	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Return the last element, reduce $n$ by 1

Heap §

Uses §

• Dijkstra’s Algorithm
• Prim’s Algorithm
• Best First Search Algorithm
• Process scheduling