1. Queue

• A queue that stores entries that have a certain order relation
• Each entry is a pair of "key and value"
• Keys in a priority queue are total order relations

2. Operation

3. Comparator

• A generic prirority queue uses an auxiliary comparator //a comparator needsed to be implemented!
• comparator(a, b) could return i < 0 if a < b, i > 0 if a > b, i = 0 if a =, or an error if not comparable

4. Implementation

Sequence-based Priority Queue

1. using an unsorted list
   • Insertion : O(1)
   • removeMin : O(n) since it has to search the smallest key(which has the highest priority)
2. using a sorted list
   • insertion : O(n) since it has to search the place where to insert the new entry
   • removeMin : O(1)

HEAP

Heap