如何使用两个队列实现优先级队列

Question

在一次面试中，我被要求使用队列实现优先队列。

面试后我搜索了一下，发现可以使用两个队列来实现，但是我没有找到具体的实现方法。

请问有人能够解释一下吗？

谢谢。

- Nagendra Yadav

---

你在哪里找到那个声明的？请发布链接。 - Bergi

“队列”上有哪些方法/访问器可用，优先队列需要什么？哪些操作需要效率？有很多可能的实现方式... - Bergi

@Bergi，你为什么认为这是来自某个网站的问题？我明确提到这是我在面试中被问到的。我是一名B科技学生，目前正在参加实习面试。如果你愿意，你可以在谷歌上搜索这个问题。 - Nagendra Yadav

@Bergi 当我搜索“如何使用队列实现优先队列”时，谷歌自动显示了建议“如何使用两个队列实现优先队列”。 - Nagendra Yadav

@Noctua，由于这个问题是在实习面试中提出的，我并不关心效率，我只需要一个简单的解决方案，以便在那里回答。我不想在生产环境或其他地方使用它。 - Nagendra Yadav

Answer 1

使用优先队列的主要优势是可以在常数时间内获取最小/最大值。因此，这应该是首要的标准。我们只考虑关键值。

我们可以使用两个队列q1和q2来创建一个优先队列。

如果输入元素大于q1的顶部，则将其附加到q1，否则

如果输入元素小于q1的顶部，则重复以下操作

从q1中删除元素并将其插入q2，直到顶部大于该元素

现在添加该元素

现在将剩余元素插入q2

so like input is 2 4 1 5 3
pass 1)
q1-> 2 
q2->  
pass 2)
q1-> 2 4
q2->
pass 3)
q1-> 
q2->1 2 4 // since 1 is less than top of q1 add it to q2 and then pop all the elements to q2
pass 4)
q1-> 
q2-> 1 2 4 5 //add it to q2 since it is larger than all the elements
pass 5)
q1-> 1 2 3 4 5//pop the elements smaller than q3 and then add the element and append the        remaining

q2->

- javacreed

Answer 2

一种基本解决方案

使用两个队列

1. 第一个队列仅包含元素

2. 第二个队列包含第一个队列中各元素的相应优先级。

   • 插入：对于每个元素，将值插入到第一个队列中，其优先级插入到第二个队列中。
                                                   时间复杂度O(1)

   • 获取顶部元素：在第二个队列中搜索最高优先级，第一个队列中相应的元素即为优先级队列的顶部元素。
                                                   时间复杂度O(n)

- Harry

---

为什么我不能在队列中使用单个队列并将值和优先级作为结构插入队列中，这样我就可以使用单个队列而不是两个队列来获取数据。 - VINOTH ENERGETIC

这不仅需要 O(n) 的时间来获取顶部元素，还会使用额外的 O(n) 空间。 - Bogdan Gavril MSFT

这个解决方案没有任何意义。为什么它被接受了？ - Ankur S

Answer 3

当然有几个选项。我能想到的第一个选项只使用1个队列，但假设您知道队列的大小。

复杂度并不好，插入将是线性的，弹出是常数级别的。

以下是伪代码Python 3。

class PriorityQueue(Queue):

    def insert(self, item):
        for i in range(self.size):
            next = self.pop()
            if next < item:
                self.enqueue(next)
            else:
                self.enqueue(item)
                self.enqueue(next)
                break
        for i in range(i, self.size):
            self.enqueue(self.pop())

    def pop(self):
        return self.pop()

我在原队列中使用了名称为'self.pop'的方法来获取第一个元素。'self.enqueue'将一个项目放在原队列的末尾。

它的工作原理是：插入操作会将所有较小的项从队列中取出并放置在末尾。当新项目是最小的时，将其放在末尾。之后，只需将其余项放在队列末尾即可。

请注意，我的代码中没有详细说明队列为空或可能已满等情况。这段代码不会起作用，但它应该能传达这个想法。

Python 3中的可行解决方案：

from queue import Queue

class PriorityQueue(Queue):

    def insert(self, item):
        if self.empty():
            self.put(item)
            return
        i = 0
        size = self.qsize()
        n = self.get()
        while item > n and i < size:
            self.put(n)
            n = self.get()
            i += 1
        if i == size:
            self.put(item)
            self.put(n)
            for i in range(size): self.put(self.get())
        else:
            self.put(item)
            self.put(n)
            for j in range(i + 1, size): self.put(self.get())

- Noctua

---

任何使用两个队列的解决方案吗？ - Nagendra Yadav

无法想到比使用2个队列的线性实现更快的方法。 - Noctua

Answer 4

这是我遇到的一些问题。 使用2个队列实现maxQueue

Dequeue时间复杂度 - O(1) Enqueue时间复杂度 - O(n)

Java代码

public class _01_MaximumQueue {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

}

public class QueueWithMax<T extends Comparable<T>> {
    Queue<T> enteries = new ArrayDeque<T>();
    Deque<T> candidatesForMax = new ArrayDeque<T>();

    public void enqueue(T x) {

        enteries.add(x);

        if (candidatesForMax.peekLast().compareTo(x) < 0) {
            candidatesForMax.removeLast();
        }
        candidatesForMax.addLast(x);

    }

    public T dequeue() {

        if (!enteries.isEmpty()) {
            T result = enteries.remove();
            if (candidatesForMax.peekFirst().equals(result)) {
                candidatesForMax.removeFirst();
            }
            return result;
        }

        throw new IllegalStateException("called Degueue() on empty Queue");
    }

    public T max() {
        if (!candidatesForMax.isEmpty()) {
            return candidatesForMax.peekFirst();
        }
        throw new NoSuchElementException("No element");
    }

}

}

- rogerTheAlien

---

队列意味着先进先出。这里既是栈又是队列，既有先进先出也有后进先出，同时具有*First和*Last方法。 - Mika Feiler