Priority queue, Comparable

Question

Hello,

I have to write a priotity queye as implementation of the folowing interface:

public interface PQueue<T extends Comparable<T>> {
   public void insert( T o );  // inserts o into the queue
   public T remove();          // removes object with highest priority (by natural order)
}

I would be glad for some help and clues, becouse I don't even know how to begin with this issue.

Answer 1

I'd start off with something like this. The general idea is that you have an internal list and when you insert a new item you do a binary search to find where it belongs in that list. This way your internal list is always sorted so when you call remove() you just take the last (or first depending on how you're ordering things) item.

Disclaimer: This should be viewed as pseudo-code. I know for a fact there are problems with it. It's only intended to be a starting point.

public class PQueueImpl<T> implements PQueue<T> {
   private List<T> internalQueue;

   public void insert(T item){
      int insertionPoint = Collections.binarySearch(internalQueue, item);
      internalQueue.add(insertionPoint, item);
   }

   public T remove(){
      return internalQueue.remove(internalQueue.size() - 1);
   }
}

Answer 2

You could look at the source for java.util.PriorityQueue. Their implementation is backed by an Object array and is significantly more complex than the other example I gave, but I'm sure it works and performs much better too.

Answer 3

Priority queues are in practice implemented most commonly as heaps. They can also be implemented as a balanced binary search tree, or any other fast sorted data structure. The key is that the data structure must have very fast (faster than O(n)) max/min, insert, remove and update operations.