如何使用优先队列实现常规队列

Question

如何使用优先队列实现常规队列?此外，我需要找到"enqueue"one_answers"dequeue"在这个方法中的运行时间。

Answer 1

您可以有一个运行索引，它记录了插入的次数，插入的第i元素的优先级为i。您总是轮询"最低"优先级元素，这是队列中最老的元素，如所需。

时间复杂度，假设您使用的是"黑盒"优先级队列，O(logn)对应popHead()和insert(), O(1)对应top()。如果您不假设"黑箱"，您可能能够调整它以更快地执行插入和删除，但是，如果您可以调整它-只需使其成为链表，或其他一些优化为队列的数据结构。

Answer 2

关于方法1的假设

1. K是与所有队列元素相关联的键

2. K是全局变量

3. Decrease-key (Q,项,K)将减小全局键值K并将新的"K"值关联起来用'item'

方法1

*ENQUE(Q, item) *

Insert(Q, item) 
Decrease-key(Q, item, K)

德,(Q)

item=Extract-Max(Q) 

方法2

*ENQUE (Q, ITEM) *

Insert(Q, item) 
Increase-key(Q, item, k) 

DE QUE (Q)

Item= Extract-Min(Q)

运行时间

1. 队列0 (1)
2. Dequeue - Log(h)其中h是二进制堆的高度

注意

1. 趋近1 - K是单调的减少
2. 趋近2 - K是单调的增加

从clr启发的书