优先级队列，可比

我必须写一个priotity queye为实现如下因素接口：优先级队列，可比

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

我会很高兴一些帮助和线索，becouse我甚至不知道如何与这个开始问题。

来源

2010-10-08 Devel

http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html？ – kennytm 2010-10-08 18:48:40

作业吗？ – 2010-10-08 18:50:05

证明你已经做出了一些努力。在线或在教科书上阅读优先队列，然后向我们展示您的尝试。 – 2010-10-08 18:51:54

我会从这样的事情开始。总的想法是，你有一个内部列表，当你插入一个新的项目，你做了二进制搜索，以找到它在该列表中的属性。这样，你的内部列表总是被排序，所以当你调用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); 
    } 
}

来源

2010-10-08 18:58:25

您可以查看java.util.PriorityQueue的源代码。它们的实现由一个Object数组支持，并且比我给出的另一个示例复杂得多，但我相信它的工作原理和性能也要好得多。

来源

2010-10-08 19:01:40

优先级队列在实践中实际上被实施为heaps。它们也可以实现为平衡的binary search tree或任何其他快速排序的数据结构。关键是数据结构必须非常快（比O（n））最大/最小速度更快，插入，删除和更新操作。

来源

2010-10-08 19:09:54 MAK

优先级队列，可比

回答

相关问题