Search code examples
algorithmgomultidimensional-arraypriority-queue

Go multi level priority queue

In Go, the container/heap package can be used as a PriorityQueue -- https://pkg.go.dev/container/heap#example-package-PriorityQueue

Is there any Go package for multi level priority queue? If not, how to write one myself?

By "multi level priority queue", here is what I mean:

  • Task 1: run through all marks from students, and get the top N students with highest marks. This is typical PriorityQueue.
  • Task 2: run through all marks from students of different courses, and get the top N highest marks for top N course (assuming the number of courses is greater than N). This is the "multi level priority queue" that I'm talking about.

Sample result can be

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

Notes,

  1. course D: with top 3 highest marks of 90 89 88 are not in top 3 courses.

  2. There might be cases that there isn't enough students marks to fill all top N highest marks. E.g.:

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

  3. Further on the requirements, In reality,

    • 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.
Solution

  • You don't need any sort of exotic queue structure to solve it. You don't even need a priority queue at all, though it's a simple way to do the select-k operation. (If you don't need your outputs to be sorted relative to each other but just be the top N in some order, it's more efficient to use a selection algorithm like quickselect.)

    For task 2, you simply need to iterate through all marks, building the top mark for each course. Once you've done that, you find the top N courses. Once you've done that, iterate through all marks again, filtering the ones for those courses into separate containers. Then just do a select-k in each one.

    The running time of this approach is O(m + N^2 log N) (where m is the total number of marks) if you use a priority queue, and O(m + N^2) if you use an efficient selection algorithm. The latter time bound is the best possible for the problem, because O(m) inputs need to be examined and O(N^2) outputs need to be generated.