python - 如何正确使用堆对 priorityqueue 进行双端队列和排序？

Question

我的作业是通过让用户以这种格式输入来创建优先级队列
案件数量
案例类型 案例ID 优先级
1 为最高优先级

Example.
16
I 0 2
I 1 2
D
I 3 3
I 4 1
D
I 6 1
D
I 8 1
D
I 10 2
I 11 1
I 12 3
I 13 2
I 14 3
I 15 2

(我指的是正常情况，D指的是当时deque最高优先级)然后按优先级排序打印剩下的caseID

这是我的代码

import heapq
priority=[]

num=int(input())
for i in range (0,num,1):
    temp=input()
    if (len(temp)>1):
        casetype,caseID,casePrio,=temp.split(" ",2)
        heapq.heappush(priority, (int(caseID),int(casePrio)))
    else:
        heapq.heappop(priority)

for i in range(len(priority)):
    print (priority[i][1]) 

我希望得到这个输出

Output:
11
1
10
13
15
3
12
14

但改用这个

Output:
11
1
10
15
12
13
14
3

Answer 1

优先级队列的整个想法是，当您弹出某些内容时，它会为您提供当前队列中优先级最高的项目。你不需要自己整理东西。那只是在做额外的工作。

如果你想按优先顺序输出队列的剩余部分，你可以用这个替换你的最终循环:

while (len(priority) > 0)
    print(heapq.heappop(priority));

每次调用 heappop 都会返回仍在队列中的最高优先级项。

但是，不要指望得到您期望的输出。 heapq 不保证具有相同优先级的项的删除顺序。例如，如果您要按此顺序插入项目:

10 1
11 2
12 2
13 3

然后删除它们，结果将是10 11 12 13。但是，如果您将插入顺序更改为:

10 1
13 3
11 2
12 2

那么输出将是10 12 11 13。