JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Publish Your Article Here

Priority Queue introduction and Java implementation


A priority queue is an abstract data type, it is like a regular queue or stack data structure, but where additionally each element has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

There are a variety of simple ways to implement a priority queue. For instance, one can keep all the elements in an unsorted list. Whenever the highest-priority element is requested, search through all elements for the one with the highest priority. In big O notation: O(1) insertion time, O(n) pull time due to search.

Below example shows basic implementation of priority queue. The condition here is, the element to be inserted should implement Comparable interface, we have taken Integer object, which is already implementing this interface.


package com.java2novice.ds.queue;

public class PriorityQueueImpl {

	@SuppressWarnings("rawtypes")
	private Comparable[] pQueue;
	private int index;
	
	public PriorityQueueImpl(int capacity){
		pQueue = new Comparable[capacity];
	}
	
	public void insert(Comparable item ){
		if(index == pQueue.length){
			System.out.println("The priority queue is full!! can not insert.");
			return;
		}
		pQueue[index] = item;
		index++;
		System.out.println("Adding element: "+item);
	}
	
	@SuppressWarnings("unchecked")
	public Comparable remove(){
		if(index == 0){
			System.out.println("The priority queue is empty!! can not remove.");
			return null;
		}
		int maxIndex = 0;
		// find the index of the item with the highest priority 
		for (int i=1; i<index; i++) { 
            if (pQueue[i].compareTo (pQueue[maxIndex]) > 0) { 
                maxIndex = i; 
            } 
        } 
		Comparable result = pQueue[maxIndex]; 
		System.out.println("removing: "+result);
		// move the last item into the empty slot 
		index--; 
		pQueue[maxIndex] = pQueue[index]; 
		return result;
	}
	
	public static void main(String a[]){
		PriorityQueueImpl pqi = new PriorityQueueImpl(5);
		pqi.insert(34);
		pqi.insert(23);
		pqi.insert(5);
		pqi.insert(87);
		pqi.insert(32);
		pqi.remove();
		pqi.remove();
		pqi.remove();
		pqi.remove();
		pqi.remove();
	}
}

Output:
Adding element: 34
Adding element: 23
Adding element: 5
Adding element: 87
Adding element: 32
removing: 87
removing: 34
removing: 32
removing: 23
removing: 5
<< Previous Program 

List of Queue Data Structure Examples

  1. Queue introduction & array based implementation
  2. Dynamic Queue implementation using arrays
  3. Double-ended queue (Decue) Implementation
  4. Double-ended queue (Decue) implementation using Doubly linked list
  5. Priority Queue introduction and Java implementation
Knowledge Centre
doPost Vs doGet methods
doGet() method is used to get information, while doPost() method is used for posting information. doGet() requests can't send large amount of information and is limited to 240-255 characters. However, doPost()requests passes all of its data, of unlimited length. A doGet() request is appended to the request URL in a query string and this allows the exchange is visible to the client, whereas a doPost() request passes directly over the socket connection as part of its HTTP request body and the exchange are invisible to the client.
Famous Quotations
The pessimist complains about the wind; the optimist expects it to change; the realist adjusts the sails.
-- William Arthur Ward

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected].

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle.
Privacy Policy | Copyright © 2019 by Nataraja Gootooru. All Rights Reserved.