在 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
筆記，
course D:前 3 名的最高分90 89 88不在前 3 名的課程中。可能存在沒有足夠的學生分數來填寫所有前 N 個最高分的情況。例如：
course E: 85 82 course F: 83 course G: 82 80 78進一步的要求，在現實中，
- 資料來自決議一個超復雜超大的 XML 檔案，因此我需要一次性遍歷XML 檔案，這就是我需要優先級佇列的原因。
- XML 檔案實際上是 SQL Server Trace 檔案，其中包含數百甚至數千條 SQL 命令（SQL 命令是課程，它們的持續時間是課程標記），這是我需要優先級佇列的第二個原因 - 僅跟蹤頂級的。
uj5u.com熱心網友回復：
您不需要任何奇異的佇列結構來解決它。您甚至根本不需要優先級佇列，盡管這是執行 select-k 操作的簡單方法。（如果您不需要將輸出相對于彼此排序，而只是按某種順序排在前 N 位，則使用快速選擇之類的選擇演算法會更有效。）
對于任務 2，您只需遍歷所有分數，為每門課程建立最高分數。完成此操作后，您會找到前 N 門課程。完成此操作后，再次遍歷所有標記，將這些課程的標記過濾到單獨的容器中。然后只需在每個中執行一個 select-k 即可。
如果您使用優先級佇列，并且如果您使用有效的選擇演算法，這種方法的運行時間是O(m N^2 log N)（其中m是標記的總數）O(m N^2)。后一個時間限制是解決問題的最佳時間，因為O(m)需要檢查輸入并O(N^2)生成輸出。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/405673.html
標籤：