刪除前面的元素並添加新的元素到最小堆（std :: priority_queue）

用例：我想爲Linux程序實現一個非常高效的發送隊列，每秒發送大量UDP數據包的速率限制流在網絡測試程序中。目前我使用的是刪除前面的元素並添加新的元素到最小堆（std :: priority_queue）

priority_queue< pair<timespec, int>, 
       std::vector<pair<timespec, int>>, 
       std::greater<pair<timespec, int>> >

程序運行正常，速度很快。但我希望能夠在一個操作中彈出隊列前面並添加一個新元素，即每個pop/emplace對只有一個重新heapify。否則，彈出窗口會重新堆砌，然後該位置會再次直接重新堆砌。

這可以用std :: make_heap，std :: push_heap和std :: pop_heap來完成嗎？或者我必須推出自己的？我當前的程序會彈出，然後在std :: priority_queue上執行emplace，這會花費'2 * O（log（N））'。

FWIW，目前的計劃是在這裏：https://github.com/alapaa/timestamping/tree/send_queue

與隊列的實際發件人是這樣的src文件： https://github.com/alapaa/timestamping/blob/send_queue/manysock/sender.cpp

來源

2017-02-09 Erik Alapää

該解決方案指出，作爲預先存在的重複（jxh：s answer）效果很好。我將它作爲std :: make_heap之上的一個小封裝類實現，請參閱https://github.com/alapaa/timestamping/blob/send_queue/manysock/send_queue.h –

使用雙端隊列作爲容器和make_heap到heapify。 - > 使用vector作爲容器，使用反向迭代器make_heap，並推回到後面。它會快一點。

vector<int> v{4,3,7,1,5}; 
make_heap(v.rbegin(), v.rend(), greater<int>()); 
for(auto& a : v) cout << a << ' '; 
cout << endl; 
q.pop_back(); 
q.push_back(9); 
make_heap(v.rbegin(), v.rend(), greater<int>()); 
for(auto& a : q) cout << a << ' '; 
cout << endl;

來源

2017-02-09 15:54:46 Parker

標準是否保證make_heap將會便宜（對數）在這個特殊情況下？我也想避免使用deque，我更喜歡速度矢量。（q的大小不會隨時間增加）。我只想將新元素放在向量的前面，然後篩選它，直到我重新建立了min-heap屬性。也許最好推出自己的。 –

如果我記得正確，make_heap與優先級隊列中使用的算法相同。所以，如果你打算使用優先級隊列，沒有理由避免使用make_heap。 – Parker

但是對於std :: priority_queue，通常只需在開始時調用make_heap（昂貴），然後經常彈出並推送元素（push和pop是對數）。 –

對不起，回答我的問題，但我沒有找到我先前的搜索這個解決方案對SO（看JXH：的答案）：How to change max element in a heap in C++ standard library?

來源

2017-02-09 16:43:37

如果另一個問題提供了您的問題的答案，那麼正確的方法是將您的問題標記爲另一個問題的[重複]（http://stackoverflow.com/help/duplicates）。不要用鏈接發佈答案。我已經投入了我的投票。 –

刪除前面的元素並添加新的元素到最小堆（std :: priority_queue）

回答

相關問題