Data Structures and Agorithm: DS 15 Priority Queue.pptx

Data Structures and Agorithm: DS 15 Priority Queue.pptx

1. Data Structure Lecture No. 15 Priority Queue Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti International Islamic University H-10, Islamabad, Pakistan Video Lecture

2. PQ using array PQ using linked list PQ using heap Priority Queue

3. #include < iostream > using namespace std ; template < typename T> class Priority_Queue { private : struct PQNode { T info; int priority; struct PQNode *next; }; PQNode * front; unsigned int sz ; public : Priority_Queue () { front = NULL; sz = 0;} ~ Priority_Queue ( ); unsigned int size () { return sz ; } void Push(T data, int priority); T Top ( ); void Pop ( ); void Show( ); }; 3 Example 1: Priority Queue using Linked List 1

4. template < class T> void Priority_Queue <T> :: Push(T data, int priority ) { PQNode * newNode , * currentNode ; newNode = new PQNode ; newNode - >info = data; newNode - >priority = priority; newNode - >next = NULL; if (front == NULL || priority < front->priority) { newNode - >next = front; front = newNode ; sz ++; } else { currentNode = front; while ( currentNode ->next != NULL && priority > currentNode ->next->priority ) currentNode = currentNode ->next; newNode ->next = currentNode ->next; currentNode ->next = newNode ; sz ++; } } 4 Example 1: Priority Queue using Linked List 2

5. template < class T> T Priority_Queue <T > :: Top ( ) { if ( front != NULL ) return front->info; return 0; } template < class T> void Priority_Queue <T> :: Pop () { PQNode * currentNode ; if (front == NULL) cout << "Priority Queue is Empty\n" ; else { currentNode = front; front = front->next; delete ( currentNode ); sz - -; } } 5 Example 1: Priority Queue using Linked List 3

6. template < class T> void Priority_Queue <T> :: Show () { for ( PQNode * t = front ; t != NULL ; t = t-> next ) cout << t->info << " " ; cout << endl ; } template < class T> Priority_Queue <T> :: ~ Priority_Queue ( ){ PQNode * currentNode ; while ( front != NULL ){ currentNode = front -> next ; delete front ; front = currentNode ; } } 6 Example 1: Priority Queue using Linked List 4

7. int main( ) { Priority_Queue < int > PQ ; PQ.Push (10,10) ; PQ.Show (); PQ.Push (15,15) ; PQ.Show (); PQ.Push (12,12) ; PQ.Show (); PQ.Push ( 3, 3) ; PQ.Show (); PQ.Push ( 4, 4) ; PQ.Show (); PQ.Push (13,13) ; PQ.Show (); PQ.Push ( 1, 1) ; PQ.Show (); PQ.Pop ( ) ; PQ.Show (); PQ.Pop ( ) ; PQ.Show (); PQ.Push ( 4, 4) ; PQ.Show (); PQ.Pop ( ) ; PQ.Show (); PQ.Pop ( ) ; PQ.Show (); PQ.Push ( 8, 8) ; PQ.Show (); system ( "PAUSE" ); return 0; } 7 Example 1: Priority Queue using Linked List 5

8. Used in certain implementation of Dijkstra ’s Shortest Path algorithm Anytime you need to dynamically fetch the “next best” or “next worst” element. Used in Huffman coding algorithm. Used in Best First Search (BFS) algorithm. Used in Minimum Spanning Tree in graphs. Applications of Priority Queue