Priority Queues

External interface

• Create (pqueue Q)

• Insert (elementtype item, pqueue Q)

• elementtype DeleteMin (pqueue Q)

Implementations

• Unsorted linked list
  • Insert is O(1); DeleteMin is O(N)

• Sorted linked list
  • DeleteMin is O(1); Insert is O(N)

• Partially ordered, balanced binary tree, where the value of a node is no greater than the value of its children (hence the minimum value is at the root). To maintain balance after deleting the root, move the rightmost leafnode to the root, and percolate it downwards based on its value. To insert, put new node at leftmost position in lowest level, and percolate upwards based on its value.
  • DeleteMin and Insert are O(log N) since the height of a balanced binary tree of N nodes is log N.