priority queue

The minimum number of queues needed to implement the priority queue is Two. One queue is used for the actual storage of data, and the other one is used for storing the priorities . Descending /max heaps are used for storing the priorities queues.

For a string priority queue , The strings are ordered inside the priority queue in lexicographic (dictionary) order

Priority Queue in Stl – heap. Priority-Queue is by default a max heap(top most node is max value)

Applications:

1. Graph Algorithms:

a. Prim’s Algorithm for Minimum Spanning Tree :  Min heap priority queue in Prim’s algorithm to find Minimum spanning tree of a connected and undirected graph

b.  Best-first search algorithm:In Best-first search algorithms, like the A* search algorithm, find the shortest path between two vertices or nodes of a weighted graph, trying out the most promising routes first. A priority queue (also known as the fringe) is used to keep track of unexplored routes; the one for which the estimate (a lower bound in the case of A*) of the total path length is smallest is given highest priority

c. Anther use case of a deque is printing a tree in zigzag manner.

d. Another is to maintain a window of elements , this would require removing elements at one end and adding at another end.

Deque has an advantage over vectors/arrays , if requirement involves adding and deleting at ends.

Use of Queue Data structure:

Problem:  Maintain a numbers of thread less than a defined value(say MAX_THREAD)such that , each thread exit after completing a task  and that thread is now available in the thread pool. This thread should be used again when a new request comes.

Solution: Create  a queue as a data member of the class. Insert values from 0 to (MAX_THREADS -1) . While queue is not empty , to create a thread,pop the front value and it would be the thread number for that thread .

When it exit add this number back to queue.This process of each new thread taking the front value from queue and pushing at back when it exit , will maintain these many threads in the system.

When queue is empty , wait for any thread to exit and then that can be used .Such a design helps in maintaining the number of threads in a system..

Same limitations can be achieved by using a stack as well