In JAVA 

Implement the Priority Queue ADT using

an Unsorted Array.

an Unsorted Linked List.

a Sorted Linked List (sort in decreasing order).

our Binary Search Tree (wrap the tree inside your priority queue implementation).

 Codes followed below //--------------------------------------------------------------------------- // PriQueueInterface.java by Dale/Joyce/Weems Chapter 9 // // Interface for a class that implements a priority queue of T. // The largest element as determined by the indicated comparison has the // highest priority. // // Null elements are not allowed. Duplicate elements are allowed. //--------------------------------------------------------------------------- package ch09.priorityQueues; public interface PriQueueInterface { void enqueue(T element); // Throws PriQOverflowException if this priority queue is full; // otherwise, adds element to this priority queue. T dequeue(); // Throws PriQUnderflowException if this priority queue is empty; // otherwise, removes element with highest priority from this // priority queue and returns it. boolean isEmpty(); // Returns true if this priority queue is empty; otherwise, returns false. boolean isFull(); // Returns true if this priority queue is full; otherwise, returns false. int size(); // Returns the number of elements in this priority queue. } 

//--------------------------------------------------------------------------- // Heap.java by Dale/Joyce/Weems Chapter 9 // Priority Queue using Heap (implemented with an ArrayList) // // Two constructors are provided: one that use the natural order of the // elements as defined by their compareTo method and one that uses an // ordering based on a comparator argument. //--------------------------------------------------------------------------- package ch09.priorityQueues; import java.util.*; // ArrayList, Comparator public class HeapPriQ implements PriQueueInterface { protected ArrayList elements; // priority queue elements protected int lastIndex; // index of last element in priority queue protected int maxIndex; // index of last position in ArrayList protected Comparator comp; public HeapPriQ(int maxSize) // Precondition: T implements Comparable { elements = new ArrayList(maxSize); lastIndex = -1; maxIndex = maxSize - 1; comp = new Comparator() { public int compare(T element1, T element2) { return ((Comparable)element1).compareTo(element2); } }; } public HeapPriQ(int maxSize, Comparator comp) // Precondition: T implements Comparable { elements = new ArrayList(maxSize); lastIndex = -1; maxIndex = maxSize - 1; this.comp = comp; } public boolean isEmpty() // Returns true if this priority queue is empty; otherwise, returns false. { return (lastIndex == -1); } public boolean isFull() // Returns true if this priority queue is full; otherwise, returns false. { return (lastIndex == maxIndex); } public int size() // Returns the number of elements on this priority queue. { return lastIndex + 1; } 

public void enqueue(T element) throws PriQOverflowException // Throws PriQOverflowException if this priority queue is full; // otherwise, adds element to this priority queue. { if (lastIndex == maxIndex) throw new PriQOverflowException("Priority queue is full"); else { lastIndex++; elements.add(lastIndex,element); reheapUp(element); } } 

public T dequeue() throws PriQUnderflowException // Throws PriQUnderflowException if this priority queue is empty; // otherwise, removes element with highest priority from this // priority queue and returns it. { T hold; // element to be dequeued and returned T toMove; // element to move down heap if (lastIndex == -1) throw new PriQUnderflowException("Priority queue is empty"); else { hold = elements.get(0); // remember element to be returned toMove = elements.remove(lastIndex); // element to reheap down lastIndex--; // decrease priority queue size if (lastIndex != -1) // if priority queue is not empty reheapDown(toMove); // restore heap properties return hold; // return largest element } }