Priority Queue

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;