Priority Queue

PRESENTATION ON PRIORITY QUEUE Submitted To Mr. Vinay Pathak Sir Mr. Rohit Katiyar Sir

SubmittedBy AnandShukla

IIIrd B.Tech I.T 219/07

Priority Queues • Priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key • A Priority Queue ranks its elements by key with a total order relation • Keys: Every element has its own key Keys are not necessarily unique • Total Order Relation, denoted by ≤ • Reflexive: k ≤ k Antisymetric: if k1 ≤ k2 and k2 ≤ k1, then k1 = k2 Transitive: if k1 ≤ k2 and k2 ≤ k3, then k1 ≤ k3

• 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:    

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:    

size add/put an element into the priority queue get element with max priority remove element with max priority

Min Heap With 9 Nodes 2

4 6

8

3 7

9

6

Complete binary tree with 9 nodes that is also a min tree.

3

Max Heap With 9 Nodes 9

8 6

5

7 7

2

1

Complete binary tree with 9 nodes that is also a max tree.

6

Heap Height Since a heap is a complete binary tree, the height of an n node heap is log2 (n+1).

Moving Up And Down A Heap 1

9 2

3

8

7

4

5 6

7

5

1

8

9

7

6 2

6

• Operations Performed on Priority Queue 1-Maximum-returns the element of S with largest key 2-Extract-Max(S)-removes and returns the element of S with the largest key 3-Increase-Key(S,x,k)-increases the value of element x’s key to a new value k which is assumed to be at least as large as x’s current key value 4-Insert(S,x)-inserts the element x into the set S. The operation could be written as S  S U {x} A min Priority Queue supports the operations INSERT, MINIMUM, EXTRACT-MIN and DECREASE-KEY

Algorithm for Fundamental Operations Heap Increase-Key(A,I,key) if key < A[i] then error “new is smaller than current key” A[i]  key while i>1 and A[parent(i)]
Max-Heap-Insert(A,key) heap-size[A]  heap-size[A]+1 A[heap-size[A]]  -infinite Heap-Increase-Key(A,heap-size[A],key)

• Heap-Maximum(A) return A[1]

• Heap-Extract-Max(A) If heap-size[A] <1 then error “heap underflow” Max  A[1] A[1]  A[heap-size[A]] Heap-size[A]  heap-size[A]-1 Max-Heapify(A,1) Return max

• The running time of Heap-Extract-Max is O(log n), since it performs only a constant amount of work on the top of the O(log n) time for Max-Heapify • The running time of Heap-Increase-Key on an n-element heap is O(log n) since path traced from node updated in line 3 to the root has length O(log n) • The running time of Max-Heap-Insert on an n-element heap is O(log n)

Putting An Element Into A Max Heap 9

8

7

6

5

7

1

75

New element is 5.

2

6

Putting An Element Into A Max Heap 9

8

7

6

5

7

1

2

20 7

New element is 20. (after this all steps belong to Heap-Increase-Key)

6

Putting An Element Into A Max Heap 9

8

7

6

5

20

1

7

New element is 20.

2

6

Putting An Element Into A Max Heap 9

20

7

6

5

8

1

7

New element is 20.

2

6

Putting An Element Into A Max Heap 20

9

7

6

5

8

1

7

New element is 20.

2

6

Putting An Element Into A Max Heap 20

9

7

6

5

8

1

2

7

Complete binary tree with 11 nodes.

6

Putting An Element Into A Max Heap 20

9

7

6

5

8

1

7

2

15

New element is 15.

6

Putting An Element Into A Max Heap 20

9

7

6

5

15

1

7

2

8

New element is 15.

6

Putting An Element Into A Max Heap 20

7

15 6

5

9

1

7

2

8

New element is 15.

6

Complexity Of Put 20

7

15 6

5

9

1

7

2

8

Complexity is O(log n), where n is heap size.

6

Removing The Max Element 20

7

15 6

5

9

1

7

2

8

Max element is in the root.

6

Removing The Max Element

7

15 6

5

9

1

7

2

8

After max element is removed.

6

Removing The Max Element

7

15 6

5

9

1

7

2

8

Heap with 10 nodes. Reinsert 8 into the heap.

6

Removing The Max Element 8

7

15 6

5

9

1

2

7

Reinsert 8 into the heap.

6

Removing The Max Element 15

8

7

6

5

9

1

2

7

Reinsert 8 into the heap.

6

Removing The Max Element 15

9

7

6

5

8

1

2

7

Reinsert 8 into the heap.

6

Removing The Max Element 15

9

7

6

5

8

1

7

Max element is 15.

2

6

Removing The Max Element

9

7

6

5

8

1

2

7

After max element is removed.

6

Removing The Max Element

9

7

6

5

8

1

7

Heap with 9 nodes.

2

6

Removing The Max Element 7

9 6

5

7 8

1

Reinsert 7.

2

6

Removing The Max Element 9

7 6

5

7 8

1

Reinsert 7.

2

6

Removing The Max Element 9

8 6

5

7 7

1

Reinsert 7.

2

6

Complexity Of Remove Max Element 9

8 6

5

7 7

2

1

Complexity is O(log n).

6

Complexity Of Operations Two good implementations are heaps and leftist trees. size, and get = rel="nofollow"> 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 8

4 1

6

2

Sorted Array

Max Priority Queue

After First Remove Max Operation 4 1

6

Max Priority Queue

2

8

Sorted Array

After Second Remove Max Operation 4 1

Max Priority Queue

2

6

Sorted Array

8

After Third Remove Max Operation

1

Max Priority Queue

2

4

6

Sorted Array

8

After Fourth Remove Max Operation Max Priority Queue

1

2

4

6

Sorted Array

8

After Fifth Remove Max Operation Max Priority Queue 1

2

4

6

Sorted Array

8

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).

Application(contd.) • One other application of max priority queue is to schedule jobs on a shared computer . The max priority queue track of the jobs to be performed and their relative priorities. When a job is finished or interrupted , the highest priority job is selected from those pending jobs using Extract-Max . A new job can be added to the queue at any time • Example- Multithreading

Application(contd.) • A min priority queue can be used in an event-driven simulator .The items in the queue are events to be simulated, each with an associated time of occurrence that serves as its key. The events must be simulated in order of their time of occurrence, because the simulation of an event can cause other events to be simulated in the future . The simulation program uses Extract-Min at each step to choose the next event to simulate, as new events are produced ,They are inserted into min priority queue using Insert.

Summary • A heap is a complete binary tree, where the entry at each node is greater than or equal to the entries in its children. • To add an entry to a heap, place the new entry at the next available spot, and perform a reheapification upward. • To remove the biggest entry, move the last node onto the root, and perform a reheapification downward.