Priority queue has, as name suggests, proproty in queue. Japanese
Usage:
- job scheduling in an operating system
- printer queues
- event-driven stimulation algorithms
Object
∀ x ∈ S ∃ priority s.t x.priority exits
Priority Queue is FIFO(first in first out), thus it is more applicable.
Operation
- Insert(S,x)
- add x in S
- returns void
- Max(S)
- returns x.priority
- Extract_max(S)
- returns x.priority
- removes x.priority from S
- Increment_priority(S, x, k)
- assign x.priority = k
List
- Unsorted List:
- Sorted List:
- Special List: maximum value of x.priority is really low
- Heap: Binary heap
Complexity
| Insert | Max | Extract_Max(Just removing） | Increment_priority | |
|---|---|---|---|---|
| Unsorted List | O(1) | O(n) | O(1) | O(1) |
| Sorted List | O(n) | O(1) | O(1) | O(n) |
| Special List | O(1) | O(k) | O(1) | O(n) |
| Heap | O(log(n)) | O(1) | O(log(n)) | O(log(n)) |
Reference
Mostly looked up on Introduction to Algorithm by Cormen, etc.