Priority Queue(Chapter 6)

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

1. Unsorted List:
2. Sorted List:
3. Special List: maximum value of x.priority is really low
4. 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.