在C++中免費實現「有界優先級隊列」

我正在尋找一個免費的軟件實現有界優先級隊列 C++中的抽象。基本上，我需要一個數據結構，其行爲就像std::priority_queue，但始終保持最「最好」的元素。在C++中免費實現「有界優先級隊列」

例子：

std::vector<int> items; // many many input items 
bounded_priority_queue<int> smallest_items(5); 
for(vector<int>::const_iterator it=items.begin(); it!=items.end(); it++) { 
    smallest_items.push(*it); 
} 
// now smallest_items holds the 5 smallest integers from the input vector

有誰知道一個良好的執行這樣的事情嗎？任何經驗與它？

來源

2011-03-16 Martin Blech

我認爲這是涵蓋在http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm – 2011-03-16 18:13:31

感嘆，購物的問題永遠不會吸吮。 – 2011-03-16 18:33:48

我認爲在this thread討論的算法可能是你在找什麼。如果你想要開始，你可能需要考慮構建Boost的實現d_ary_heap_indirect這是Boost.Graph的一部分（在d_ary_heap.hpp）。如果你做得很好，你可以將它提交給Boost。它可以做一個很好的補充，因爲這樣的實現肯定有很多用途。

來源

2011-03-16 20:46:25

爲什麼不將std :: vector與函子/比較函數和std :: sort（）一起使用到正確的順序？該代碼可能相當微不足道

來源

2011-03-16 17:52:04 Jay

在某些情況下，這可能會比堆更差。 – 2011-03-16 18:12:15

在C++中免費實現「有界優先級隊列」

回答

相關問題