Priority Queue

A priority queue is an Abstract Data Type consisting of a collection of items(each having a priority) with operations:

• insert: inserting an item tagged with a priority
• deleteMax: removing and returning the item of highest priority
  • deleteMax is also called extractMax or getmax.
  • priority is also called key

$\to$ Above definition is a maximum-oriented priority queue. A minimum-oriented priority queue is defined in the natural way, replacing operations deleteMax by deleteMin.

Applications: typical “todo” list, simulation systems, sorting

Using Priority Queue to Sort

Pseudocode: Note: run-time depends on how priority queue is implemented Sometimes written as: $O(initialization+n\ast insert+n\ast deleteMax)$

Realizations

Realization 1: unsorted arrays

• insert $\to O(1)$
  • adding element at the end of the array or list
• deleteMax $\to O(n)$
  • Finding and removing the max element from an unsorted array or linked list requires scanning through the entire array or list to identify the max element to remove. Note: we assume dynamic arrays Using unsorted linked lists is identical PQ-sort with this realization yields Selection Sort $\to$ since the selection sort algorithm has an average and worst-case time complexity of $O(n^2)$.

Realization 2: sorted arrays

• insert $\to O(n)$
  • Inserting an element requires finding the correct position, involves searching through the elements to find the right position. Worst-case, it requires iterating over all $n$ elements resulting in $O(n)$.
• deleteMax $\to O(1)$
  • Max element is at the end, therefore removing max element can be done in constant time by simply deleting the last element. Using sorted linked lists is identical PQ-sort with this realization yields Insertion Sort $\to$ time complexity similar to insertion sort algorithm which has an average and worst-case time complexity of $O(n^2)$ but can be improved to $O(n)$ in the best case for partially sorted input.

Note

The choice of data structure realization for the priority queue affects the efficiency of PQ-sort algorithm and the resulting sorting algorithm.

Questions

• What operations must Priority Queue support?
  • deleteMax/deleteMin
  • insert
• Possible realization of PQ ADT?
  • unsorted array
  • sorted array
  • linked list
  • binary heap
  • binary search tree
  • ternary heap
  • Vector