Priority Queue

•  Example : Job Scheduler , Key = Priority

• Operations:

•
Construct                                                         = ( Insert )^N
* Insert
* Remove         largest  element
Replace(v)    largest with new item v         =  Insert + Remove
Change          priority of an element           = Delete + Insert
Join                2 queues
Delete

• Priority Queue  for  Sorting = (Insert)^N(Remove)^N
• 1) unordered list  ==> Selection  Sort  : burden on remove
2) ordered list      ==> Insertion Sort   : burden on insert
3) Heap              ==> Heap Sort        : amortize
T = NLogN

• Heap
•

 a[j] >= a[2j]        >= a[2j+1]

 i 1 2 3 4 5 6 7 8 9 10 11 12 a[i] X T O G S M N A E R A I

 UpHeap(K) Insert(V) N:=N+1;  a[N]:=V;  Upheap:=(N); DownHeap(K) Replace(V) a[0]:=V;  DownHeap(0);  replace:=a[0]; Remove remove := a[1];  a[1]:=a[N];  N:=N-1;  DownHeap(1);
T = O (logN)

• Heap Sort

 (1)   (Insert)^M(Remove)^M  (2)       N:= M;       for  K:=M/2 downto 1       do            DownHeap(K);         repeat            swap(a[1],a[N]);            N : = N-1;            DownHeap(1);       Until N<=1;

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

 A S O R T I N G E X A M P L E N L E P M I X T A R G E P O N M I L E X R T G E S A X T P R S O N G E A A M I L E T S P R E O N G E A A M I L S R P L E O N G E A A M I R L P I E O N G E A A M P L O I E M N G E A A O L N I E M A G E A N L M I E A A G E M L E I E A A G L I E G E A A I G E A E A G E E A A E A E A E A A A A A A A E E G I L M N O P R S T X