java - 优先队列，可比

Question

我必须编写一个优先队列作为以下接口(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)
}

我很乐意提供一些帮助和线索，因为我什至不知道如何开始这个问题。

Answer 1

我会从这样的事情开始。一般的想法是你有一个内部列表，当你插入一个新项目时，你会进行二进制搜索以找到它在该列表中的位置。这样你的内部列表总是排序的，所以当你调用 remove() 时，你只需要最后一个(或第一个取决于你订购东西的方式)项目。

免责声明:这应被视为伪代码。我知道这是有问题的。它只是一个起点。

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);
   }
}