Go多级优先级队列

Question

在Go中，container/heap包可以用作PriorityQueue -- https://pkg.go.dev/container/heap#example-package-PriorityQueue

是否有用于多级优先级队列的Go包？如果没有，自己怎么写呢？

关于“多级优先级队列”，我的意思是：

• 任务1:通过学生的所有分数，得到得分最高的N名学生。这是典型的PriorityQueue.
• Task 2:遍历来自不同课程的学生的所有分数，并获得顶级N门课程的最高N分(假设课程数量大于N)。这是我所说的“多级优先级队列”。

样本结果可以

course A: 99 98 98 
course B: 92 90 88
course C: 91 89 87

笔记，

1. course D:的90 89 88排名前三名，但没有进入前三名。

1. 可能有这样的情况:没有足够的学生分数来填补所有最高的N分。例如：

课程E: 85 82课程F: 83课程G: 82 80 78

1. 进一步讨论了需求，实际上，

- the data come from parsing a super complicated and super large XML file, thus I need to walk the XML file in a _single pass_, that's why I need the priority queue.
- the XML file is actually SQL Server Trace file, which contains hundreds or even thousands of SQL commands (the SQL commands being the courses, and their duration being course marks), that's the second reason that I need the priority queue -- to track only the top ones.

Answer 1

您不需要任何外来的队列结构来解决它。您甚至根本不需要优先级队列，尽管这是执行select-k操作的简单方法。(如果不需要对输出进行相对排序，而只是按某种顺序排序，那么使用像quickselect这样的选择算法会更有效。)

对于任务2，您只需迭代所有分数，为每门课程建立最高分。一旦你这样做了，你就会找到顶尖的N级课程。一旦您这样做了，再次遍历所有的标记，将那些课程的标记过滤到单独的容器中。然后在每一个中做一个选择-k。

如果使用优先级队列，则该方法的运行时间为O(m + N^2 log N) (其中m是标记总数)，如果使用有效的选择算法，则为O(m + N^2)。对于这个问题，后一个时间限制是最好的，因为需要检查O(m)输入，需要生成O(N^2)输出。