雙重優先級隊列

Question

我有一組數據，我想查找最大和最小的項目（多次），那麼執行此操作的最佳方法是什麼？

對於任何對該應用程序感興趣的人，我正在開發一個詳細的系統級別，我需要找到具有最大和最小屏幕空間錯誤的項目，顯然每次我細分/合併一個項目時，我必須插入它進入排隊，但每次相機移動整個數據集的變化 - 所以它可能是最好的，只是使用排序列表，並推遲添加新的項目，直到下一次我排序（因爲它經常發生）

Answer 1

您可以使用如文中所述的最小 - 最大堆Min-Max Heaps and Generalized Priority Queues：

的簡單實現雙倍結束的優先級隊列爲 。建議的結構， 稱爲最小 - 最大堆，可以在 內建線性時間;與傳統堆中的 相比，它允許在 恆定時間內執行FindMin和FindMax兩個 ; Insert，DeleteMin和 DeleteMax操作可以在對數時間執行 。