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

Question

在面试问题中,我被要求使用队列实现优先级队列,

在采访之后我用Google搜索并发现它可以使用两个队列实现,但我没有找到如何...

请任何人解释我.

提前致谢.

Answer 1

使用优先级队列的主要优点是我们可以在恒定时间获得最小值/最大值.所以这是应该满足的第一个标准.我们只考虑关键价值观.我们可以使用两个队列创建一个prioity队列,如果输入元素大于q1的顶部,则将它们命名为q1和q2,然后将其附加到q1 else

如果输入小于q1的顶部,则重复

从q1中删除元素并插入到q2,直到top大于该元素

现在添加元素

现在将剩余的元素插入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->

Answer 2

一个基本的解决方案

使用两个队列

1. 第一个仅包含所有元素

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

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

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