Sorted list implementation: Like a checkout line at the supermarket, but where important people get to “cut” in front of less important people. (if using a basic array/list, this takes O(n) insertion time, O(1) pullNext time (from the front), and on average O(n*log(n)) to initialize (if using quicksort) or O(N^{2}) for insertion sort – Wikipedia

class Node
{
public int item;
public Node next;
public Node(int val)
{
item = val;
}
}
class PQSort
{
private Node first;
public PQSort()
{ first = null; }
public void insert(Node k)
{
Node previous = null;
Node current = first;
while(current != null && k.item > current.item)
{
previous = current;
current = current.next;
}
if(previous==null)
first = k;
else
previous.next = k;
k.next = current;
}
public Node pop()
{
Node temp = first;
first = first.next;
return temp;
}
}
class PriorityQueue
{
public static void main(String[] args)
{
int size = 10;
PQSort thePQSort = new PQSort();
for(int j=0; j<size; j++)
{
int n = (int)(java.lang.Math.random()*99);
Node newLink = new Node(n);
thePQSort.insert(newLink);
}
System.out.println("Inserted elements at random into the queue such that Priority queue contains highest element at the end");
System.out.println("sorted List based on Priority Queue . removing minimum element from the front of the list and displaying: ");
for(int j=0; j<size; j++)
System.out.print(thePQSort.pop().item + " ");
System.out.println("");
}
}

OUTPUT:

~/PriorityQSort$ java PriorityQueue

Inserted elements at random into the queue such that Priority queue contains highest element at the end

sorted List based on Priority Queue . removing minimum element from the front of the list and displaying:

10 32 35 37 45 47 56 63 67 84

Efficient way of implementing a Priority queue is by using a heap O(nlog(n))

### Like this:

Like Loading...

*Related*

Bugs dude.

if(previous==null){

k.next = first;

first = k;

}