去多级优先队列

Question

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

是否有用于多级优先级队列的 Go 包？如果没有，如何自己写一个？

通过“多级优先级队列”，我的意思是：

• 任务1：遍历学生的所有分数，得到分数最高的前N名学生。这是典型的 PriorityQueue。

• 任务2：遍历不同课程学生的所有分数，得到前N门课程的前N高分（假设课程数大于N）。这就是我所说的“多级优先级队列” 。

样本结果可以是

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

笔记，

1. course D:前 3 名的最高分90 89 88不在前 3 名的课程中。

2. 可能存在没有足够的学生分数来填写所有前 N 个最高分的情况。例如：

   course E: 85 82
   course F: 83
   course G: 82 80 78

3. 进一步的要求，在现实中，

• 数据来自解析一个超复杂超大的 XML 文件，因此我需要一次性遍历XML 文件，这就是我需要优先级队列的原因。

• XML 文件实际上是 SQL Server Trace 文件，其中包含数百甚至数千条 SQL 命令（SQL 命令是课程，它们的持续时间是课程标记），这是我需要优先级队列的第二个原因 - 仅跟踪顶级的。

Answer 1

您不需要任何奇异的队列结构来解决它。您甚至根本不需要优先级队列，尽管这是执行 select-k 操作的简单方法。（如果您不需要将输出相对于彼此排序，而只是按某种顺序排在前 N 位，则使用快速选择之类的选择算法会更有效。）对于任务 2，您只需遍历所有分数，为每门课程建立最高分数。完成此操作后，您会找到前 N 门课程。完成此操作后，再次遍历所有标记，将这些课程的标记过滤到单独的容器中。然后只需在每个中执行一个 select-k 即可。如果您使用优先级队列，并且如果您使用有效的选择算法，这种方法的运行时间是O(m + N^2 log N)（其中m是标记的总数） 。O(m + N^2)后一个时间限制是解决问题的最佳时间，因为O(m)需要检查输入并O(N^2)生成输出。