priority queue:

4 A priority queue is a queue that contains items that have some preset priority.

4 When an element has to be removed from a priority queue, the item with the highest priority is removed first.

4 Priority queue can be represented using heaps. A heap node contains the value in every node is at least as large as the values in the child nodes.

In a priority queue, elements are inserted as per their priority levels. And when removing a node with highest priority must be removed first. When all elements with highest priority are removed, it removes nodes with next highest priority.

Applications of priority queue:

To find k^th largest element: To find k^th biggest element in a list of elements a priority queue can be maintained to indicate their corresponding degree. And the required element can be directly picked up.

Sorting: Some sorting techniques use priority queues for implementing sorting.

Event simulation: A simulation consists of processing events. The events with priority levels are loaded onto a priority queue and processed as per their priorities.

Job scheduling: In the application of job scheduling, jobs with priority are entered into the queue and the job with highest priority is chosen for execution.

Program to implement a priority queue:

class PriorityQ

{

private int a[]=new int[10];

private int n;

PriorityQ()

{

n = 0;

}

public void insert(int v)

{

int i;

if (n==0)

a[n++]=v;

else

{

for (i=n-1;i>=0;i--)

{

if (v>a[i]) // if new v is larger,

a[i+1] = a[i]; // shift upward

else

break;

}

a[i+1] = v;

n++;

}

}

public int delete()

{

return a[--n];

}

public void show()

{

System.out.println("\n Priority Queue Elements:");

for(int i=0;i

System.out.print("\t"+a[i]);

}

}

class PQueueTest

{

public static void main(String[] args)

{

PriorityQ p1 = new PriorityQ();

p1.insert(30);

p1.insert(20);

p1.insert(50);

p1.insert(10);

p1.show();

p1.delete();

System.out.println("\n After Deleting:");

p1.show();

}

}

/* Output */

Priority Queue Elements:

50 30 20 10

After Deleting:

Priority Queue Elements:

50 30 20