FIT1008 Lecture Notes - Lecture 12: Priority Queue, Job Scheduler, List Of Algorithms
18 Jun 2018
School
Department
Course
Professor
Priority'queue'ADT
Each%element%has%a%numeric%priority.
Highest-priority%element%is%processed%first.
Lowest%in%a%dual%implementation
○
FIFO%if%priority%is%assumed%to%be%time%spent%in%queue
○
•
Applications:
Hospital%emergency%rooms
•
Job%scheduling
•
Discrete%event%simulations
•
Graph%algorithms
•
Ops:
__init__(self)
•
__len__(self)
•
is_empty(self)
•
add(key, element) (adds%element%to%priority%queue)
•
get_max() (returns%max%element%and%removes%it%from%queue)
•
What%data%structures%can%support%the%implementation%of%this?
Array-based%and%linked%lists%(sorted%too)
•
Binary%search%trees
•
Binary-tree-and%array-based%heaps
•
Data%struc
get_max() complexity
add() complexity
Array-based%list
O(n)
O(1)
Linked%list
O(n)
O(1)
Sorted%array-
based%list
O(1)%[position%=%count(-1%depending%on%
if%max%or%min)]
O(n)%[find%right%
position]
Sorted%linked%list
O(1)%[at%head]
O(n)%[find%right%
position]
Heap
Better%implementation%than%priority%queue,%since%both%BST%methods%have%one%
O(n)%operation
Would%be%O(depth)%for%the%binary%tree%with%depth%being%N-1%if%unbalanced
•
All%levels%are%filled,%except%possibly%the%last%one,%which%is%filled%left%to%right
•
When%adding new%element,
Put%at%bottom%according%to%order%of%0,1,00,01,10,11,…•
Rise while%order%is%broken•
Best%case:%O(1) When%the%item%is%smaller/equal%to%parent,%no%need%to%rise
Worst%case:%O(logN) When%item%rises%all%the%way%to%the%top
logN%=%[depth]%number%of%iterations%of%loop%in%rise
Min-heap (smallest%value%always%root%node)
For%every%node,
Values%of%children%>=%value%at%node•
Resulting%array%will%always%be%min%->%max
Max-heap (largest%value%always%root%node)
For%every%node:
Values%of%children%<=%value%at%node•
When%adding%a%new%node%larger%than%parents,%swap%until%parent%is%of%new%node%is%
greater/equal.%(require%reference%to%parent)
To%get%maximum value,%
Swap%root%with%last%item•
Remove%last%item•
Sink while%order%is%broken•
Best%case:%O(1) When%item%is%>=%largest%children
Worst%case:%O(logN) When%item%sinks%all%the%way%to%the%bottom
logN%=%[depth]%number%of%iterations%of%loop%in%sink
Implementation:
Binary%tree%of%linked%nodes?
Requires%extra%references%to%rise%a%node/move%up%the%tree%-extra%memory•
Array?
Possible%due%to%completeness%of%binary%tree•
Very%compact•
Parent%position Child%left Child%right
0%(root) 1 2
1 3 4
2 5 6
3 7 8
4 9 10
k2k+1 2(k+1)
Parent%position Child%left Child%right
1%(root) 2 3
2 4 5
3 6 7
4 8 9
510
k2k 2k+1
With%shift,
Root%at%position%1•
Children%of%k%(if%they%exist):%2k%and%2k+1•
Parent%of%k%(except%for%root):%k//2•
Heap'sort
=%adding%elements%of%the%list%into%a%heap,%then%removing%them
log(n)%+%log(n)%=%2log(n)%-->%nlog(n)
For%each%element%in%array,%add%to%heap O(logN)
While%heap%contains%elems,%get%max%item O(logN)
Worst%case:%nlog(n)
Week$12:$Priority$queue,$heap
Friday,%15%June%2018
16:30
Document Summary
Fifo if priority is assumed to be time spent in queue. __len__(self) is_empty(self) add(key, element) (adds element to priority queue) get_max() (returns max element and removes it from queue) O(1) [position = count(-1 depending on if max or min)] Better implementation than priority queue, since both bst methods have one. Would be o(depth) for the binary tree with depth being n-1 if unbalanced. All levels are filled, except possibly the last one, which is filled left to right. Put at bottom according to order of 0,1,00,01,10,11, . When the item is smaller/equal to parent, no need to rise. Worst case: o(logn) when item rises all the way to the top logn = [depth] number of iterations of loop in rise. Resulting array will always be min -> max. When adding a new node larger than parents, swap until parent is of new node is greater/equal. (require reference to parent)
