ISourceCode

Make the frequent cases fast and the rare case correct

Priority Queue based on Sorted Linked Lists

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(N2) 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))

One response to “Priority Queue based on Sorted Linked Lists

  1. Denly Shih December 4, 2015 at 12:18 pm

    Bugs dude.
    if(previous==null){
    k.next = first;
    first = k;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: