优先队列的块(数组)实现？

Question

我现在正在准备考试，在样本考试中遇到了这个问题：

优先级队列的阻塞实现

如果我们预先知道优先级队列将只需要满足少量离散优先级(例如10个)，我们可以通过将优先级队列表示为队列数组来在恒定时间内实现优先级队列的所有操作-每个队列存储单个优先级的元素。注意，尽管操作可以在优先级队列中的优先级数量上是线性的，但是该操作相对于整个数据结构的大小仍然是恒定的。

存储在此优先级队列中的对象是不可比较的。

我已经尝试过了，但我不知道如何使用数组实现优先级队列来分配优先级。

我也尝试过寻找解决方案，但我所找到的都是使用可比较的例子，这是我们在本课程中没有学到的。

问题：http://imgur.com/3mlBoW7

Answer 1

每个数组将对应不同的优先级。您的最低优先级数组将只处理该优先级的对象。您的最高优先级数组将处理最高优先级的对象，依此类推。当您接收到新对象时，将其放入与其优先级相对应的数组中。

因此，对象是不可比较的，这并不重要，因为它们是根据数组的分层按优先级排序的。然后，当您查找要执行的下一个元素时，检查最高优先级的数组并查看是否有任何元素；如果没有，则移动到下一个优先级，依此类推，遍历每个数组。

我希望我正确理解了这个问题和你的问题；如果你对我的回答还有其他问题，请告诉我。

Answer 2

根据Imcphers的回答，这将是一个简单的Java实现。注意，您不需要Comparable，因为enqueue需要一个额外的参数，即新添加元素的离散优先级：

public class PQueue<T> {
     public static final int MAX_PRIORITIES = 10;
     private ArrayList<ArrayDeque<T> > queues = new ArrayList<>();
     public PQueue() {
         for (int i=0; i<MAX_PRIORITIES; i++) {
             queues.add(new ArrayDeque<T>());
         }
     }
     public void enqueue(int priority, T element) {
         // ... add element to the end of queues[priority]
     }
     public T dequeue() { 
         // ... find first non-empty queue and pop&return its first element
     }
     // ... other methods
}

这里，enqueue()和dequeue()都是O(1)，因为您预先知道可以有多少优先级，以及它们的值是什么(0到MAX_PRIORITIES 1)，因此不需要排序，并且搜索非空队列的时间是恒定的(至多，必须测试MAX_PRIORITIES队列是否为空)。如果这些参数未知，则最佳实现将使用

 private TreeSet<ArrayDeque<T extends Comparable> > queues 
      = new TreeSet<>(CustomComparator);

其中CustomComparator要求队列根据其第一个元素的自然顺序进行自我排序，并且需要在每次调用enqueue之后保持这些内部队列的排序-这会将入队/出队的复杂性提高到O(log )，其中p是不同优先级的数量(因此，内部队列也是如此)。

注意，Java的PriorityQueue属于相同的复杂性类，但是通过实现自己的内部优先级堆，避免了TreeSet / ArrayDeque包装器带来的所有对象开销。