Java优先级队列接口实现

这是几天前我在面试中被问到的问题，我对这种方法并不确定。建议将高度赞赏：Java优先级队列接口实现

我怎么能实现Queue接口获得队列（）方法在O（1）和出队（）在O（n）的方法。

我怎么能实现Queue接口获得队列（）方法在O（n）和出队（）方法在O（1）。

谢谢。

来源

2010-07-24 Rachel

这是一个棘手的问题，希望的位置是一个有信誉的一个。 – mdma 2010-07-24 00:13:02

嗯......我以为是。 – Rachel 2010-07-24 00:20:11

@mdma - 你在开玩笑吗？或者你真的认为你的评论。 – Rachel 2010-07-25 13:03:46

一个典型的PriorityQueue实现将使用堆以获取“添加”操作O（LG n）性能，所以O（n）性能会更容易。

例如，你可以使用一个载体或链表作为底层数据结构。对于O（1）“添加”，您可以简单地将新值添加到末尾，对于O（n）“移除”，您可以对最小值进行线性搜索。相反，对于O（n）“添加”，您可以执行线性扫描以查找下一个最大值，然后插入它，对于O（1）删除，您可以简单地删除列表的第一个元素。

来源

2010-07-24 00:15:48 maerics

对于O（1）的方式来你必须保持跟踪你的队列的最后一个元素，让您可以轻松地多了一个附加后，您的队列无论大小队列（）方法。

对于queue（）中的O（n）和dequeue（）中的O（1），您需要跟踪变量中队列的第一个元素，以便不管内部元素的数量如何可以通过一组指令（不重复）从列表中删除第一个。

在每个两种情况下你只需要添加一个额外的变量到类。

来源

2010-07-24 00:15:57

你能给出一个相同的代码示例吗？这里很难理解。 – Rachel 2010-07-24 00:20:43

嗯，我现在还没有一个方便的方法，但是通过使用节点来实现自己创建的Java PriorityQueue，您可以轻松实现这一目标。制作节点类，其中节点是具有对象的实体，并且是对下一个节点的引用。然后创建一个列表，它获得了第一个节点/最后一个节点的引用[取决于您是否希望O（1）用于排队或出队或两者]，然后完成！我不知道核心Java的PriorityQueue类是如何实现的，但它也可能以这种方式或类似的方式实现。检查源代码可能会成为一个例子。 – 2010-07-24 00:37:57

只要看一看：

http://www.docjar.com/html/api/java/util/PriorityQueue.java.html

请记住，所有优秀的程序员复制好的代码：P

我假设你有关于数据结构，列表，地图等基本的了解如果你不知道，理解这项工作如何没有多大意义，那就去进一步调查一下这个问题。

来源

2010-07-24 00:16:18

队列（）在O法（1）的O型出队（）方法（N）：

使用链表，干脆直接在队列中每增加一个新条目列表的头（）。在dequeue（）中迭代列表并删除并返回具有最高优先级的条目。

队列（）中O的方法（n）和出队（）中O的方法（1）：

再次使用一个链表。但是这次在queue（）中迭代条目以将新条目放入其优先排序位置（实际上这是插入排序的一个步骤）。在dequeue（）中，您现在可以始终删除并返回列表的第一个元素。

来源

2010-07-24 00:20:05 x4u