優先級隊列隨機訪問

Question

我有優先級隊列，通過某個值對元素進行排序（讓它命名爲評級）。我需要按排名從隊列中獲取元素。所以我需要實現函數queue_get（rating）。該功能還可以提高優先級堆棧的可用性。

但問題是堆的每個級別都沒有按評級排序。每個級別的元素只滿足堆屬性。所以我不能通過評級返回第N個元素。

有這種功能的優先級隊列的任何實現嗎？ 我應該使用其他數據結構嗎？

Answer 1

最簡單的解決方案是使用自平衡的二叉搜索樹， AVL樹，松樹或紅黑樹。它允許你在O（log n）時間內通過它們的鍵來訪問元素，並按O（log n + k）中的順序迭代對象，其中k是迭代元素的數量。

Answer 2

集合類通常會爲您提供一些基於有序鍵的Map，如java.util.TreeMap或C++ std :: map。使用此功能，您可以按排序順序檢索項目 - 如果班級按順序遞增項目，則可能必須顛倒順序。如果你想要做的只是讀取前N項，這對你來說應該足夠了。

如果要隨機訪問第N個最高項目，可以通過使用每個節點下的項目數目註釋樹數據結構來完成此操作，但我不知道有一個廣泛可用的類庫可以爲您提供此功能。

想想吧，如果您只想按順序檢索N個最高的項目，您可以在優先隊列中執行此操作，只要您準備在讀取項目時移除項目並將其重新放回稍後如果您需要恢復原始內容。