0

Use case: I want to implement a very efficient send queue for a Linux program sending many rate-limited streams of large numbers of UDP packets per second in a network test program. Currently, I use a 

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

The program functions correctly and is fast. But I would like to be able to pop front of queue and add a new element in one operation, i.e. only one re-heapify per pop/emplace pair. Otherwise, the pop will re-heapify, and then the emplace will directly re-heapify again.

Can this be done with std::make_heap, std::push_heap and std::pop_heap? Or do I have to roll my own? My current program does pop followed by emplace on the std::priority_queue, which costs '2*O(log(N))'.

FWIW, the current program is here: https://github.com/alapaa/timestamping/tree/send_queue

The actual sender with queue is this src file: https://github.com/alapaa/timestamping/blob/send_queue/manysock/sender.cpp

Improve this question
1

2 Answers 2

Reset to default
0

Sorry for answering my own question, but I did not find this solution in my earlier searches on SO (look at jxh:s answer): How to change max element in a heap in C++ standard library?

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

if another question provides the answer to your question, then the correct approach is to mark your question as a duplicate of the other one. Not to post an answer with a link. I've put in my vote to do so.
0

Use deque as a container and make_heap to heapify. --> Use vector as a container and make_heap using reverse iterator, and push at the back. It will be a little faster.

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;
Improve this answer

8 Comments

Does the standard guarantee that make_heap will be cheap (logarithmic) in this special case? I also would like to avoid using a deque, I prefer vector for speed. (size of q will not increase over time). I would like to just put the new element at the front of the vector, and then sift it down until I have re-established the min-heap property. Maybe best to roll my own.
If I am remembering correctly, make_heap is the same algorithm that is used in priority queue. So, if you intend to use priority queue, there is no reason to avoid using make_heap.
But for a std::priority_queue, you often just call make_heap once at the beginning (expensive), then just pop and push elements often (push and pop are logarithmic).
I wanted to say that the cost of using pri queue is more than using make_heap.
Why? std pri q is just an adapter/wrapper over make_heap, push_heap and pop_heap. And the algorithmic complexity is as it should be in a heap.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.