priority queue

Property: A regular Queue of elements where each element has a priority

AND we are only interested in the HIGHEST priority element.

Operation: add, remove

PQ.add(obj)

PQ.remove(&obj) // remove highest priority element

------

Implementation Option 1 --- queue sorted by priority

add element to PQ

• use insert-in-order, the insertion sort technique, to maintain priority sorted order

• add complexity is O(n)

remove highest priority element

• head of PQ is the highest priority element

• remove complexity is O(1) if PQ is a list

• remove complexity is O(n) if PQ is an array

  • if all we need is ONLY to determine the highest priority element

  • tree like algorithm with array based implementation

  • elegant and fast

Implementation Option 2 --- multiple queues, each priority has its own queue

Technically, this approach does not qualify as "priority queue". However, it is very practical in applications, especially if there are only a very limited number of priorities.

add element to MQ

• add complexity is O(1), assume you have tail

remove highest priority element

• head of highest priority MQ, if it is not empty

• remove complexity is O(1) if # of priority is finite

<<NOTE>> If each element has a distinct priority, then each queue has only one element. The implementation will be the same as single priority queue PQ mentioned above.

Implementation Option 3 --- a heap

• tree like algorithm with array based implementation

• elegant and fast

  • add complexity is O(log n)

  • remove complexity is O(log n), but it can be O(1)

• more on heap page