Max Priority Queue Collection of elements.
Each element has a priority or key.
Supports following operations:
isEmpty
size
add/put an element into the priority queue
get element with max priority
remove element with max priority
Priority Queues Two kinds of priority queues:
Min priority queue.
Max priority queue.
Min Priority Queue Collection of elements.
Each element has a priority or key.
Supports following operations:
isEmpty
size
add/put an element into the priority queue
get element with min priority
remove element with min priority
Max Priority Queue Collection of elements.
Each element has a priority or key.
Supports following operations:
isEmpty
size
add/put an element into the priority queue
get element with max priority
remove element with max priority
Complexity Of Operations Two good implementations are heaps and leftist trees.
isEmpty, size, and get => O(1) time
put and remove => O(log n) time where n is the size of the priority queue
Applications Sorting
use element key as priority
put elements to be sorted into a priority queue
extract elements in priority order
if a min priority queue is used, elements are extracted in ascending order of priority (or key)
if a max priority queue is used, elements are extracted in descending order of priority (or key)
Sorting Example Sort five elements whose keys are 6, 8, 2, 4, 1 using a max priority queue.
Put the five elements into a max priority queue.
Do five remove max operations placing removed elements into the sorted array from right to left.
After Putting Into Max Priority Queue Sorted Array
6 8 2 4 1 Max Priority Queue
After First Remove Max Operation Sorted Array
6 2 4 1 8 Max Priority Queue
After Second Remove Max Operation Sorted Array
2 4 1 8 6 Max Priority Queue
After Third Remove Max Operation Sorted Array
2 1 8 6 4 Max Priority Queue
After Fourth Remove Max Operation Sorted Array
1 8 6 4 2 Max Priority Queue
After Fifth Remove Max Operation Sorted Array
8 6 4 2 1 Max Priority Queue
Complexity Of Sorting Sort n elements.
n put operations => O(n log n) time.
n remove max operations => O(n log n) time.
total time is O(n log n).
compare with O(n2) for sort methods of Chapter 2.
Heap Sort Uses a max priority queue that is implemented as a heap.
Initial put operations are replaced by a heap initialization step that takes O(n) time.
Machine Scheduling m identical machines (drill press, cutter, sander, etc.)
n jobs/tasks to be performed
assign jobs to machines so that the time at which the last job completes is minimum
Machine Scheduling Example 3 machines and 7 jobs
job times are [6, 2, 3, 5, 10, 7, 14]
possible schedule
A B C time -----------> 6 2 3 7 13 13 21
Example schedule is constructed by scheduling the jobs in the order they appear in the given job list (left to right); each job is scheduled on the machine on which it will complete earliest.
Machine Scheduling Example Finish time = 21
Objective: Find schedules with minimum finish time.
A B C time -----------> 6 2 3 7 13 13 21
LPT Schedules Longest Processing Time first.
Jobs are scheduled in the order
14, 10, 7, 6, 5, 3, 2
Each job is scheduled on the machine on which it finishes earliest.
LPT Schedule [14, 10, 7, 6, 5, 3, 2]
A B C 14 10 7 13 15 16 16 Finish time is 16!
LPT Schedule LPT rule does not guarantee minimum finish time schedules.
(LPT Finish Time)/(Minimum Finish Time) <= 4/3 - 1/(3m) where m is number of machines.
Usually LPT finish time is much closer to minimum finish time.
Minimum finish time scheduling is NP-hard.
Comments