CODEWITHSUNDEEP
c++stlheap
LiKao
LiKao

Reputation: 10658

How to handle heaps in C++

I know this is probably one of those "you just have to try it" kind of questions, but since I do not have actual test data available yet, I'd like to get some input on your experience while I am still designing the code.

I have a data structure that implements a priority queue with some added functions. What I usually need to do is adding a bunch of objects to this heap at a time. I am using the std::make_heap(), std::push_heap() and std::pop_heap() algorithms to maintain the heap invariants.

For now whenever I do an insert I use std::push_heap() to add the single element. Now I am thinking about adding all the elements at a time, using the std::vector::push_back() method and then reorganizing the heap. A simple push_heap() at this time probably won't work so I would have to use a new make_heap(). However make_heap() runs in (3*(last-first)) while push_heap() only takes log(last-first).

Is there a simple way to figure out which one is actually faster in this case, or do I have to wait until test data becomes available?

Upvotes: 3

Views: 410

Answers (2)

sth
sth

Reputation: 229914

If you insert k elements into a heap of size n, make_heap() will be faster roughly from the point where k⋅log2(n) > 3⋅n. That means when k > 3⋅n / log2(n). You could calculate this value before a mass insertion and then decide what method will be faster.

Note that this value is only a rough estimation, because the actual implementation of the function probably won't take exactly these times to perform the operations. But it should be useful as a rule of thumb and get reasonably good results.

Upvotes: 4

David Thornley
David Thornley

Reputation: 57076

make_heap runs with no more than 3N comparisons (where N is the size of the heap), while push_heap takes no more than log N. However, you have to push each element into the heap separately, which means it takes N push_heaps, so that method is bounded by N log N comparisons.

Therefore, make_heap is asymptotically better than N push_heaps. If the heap is large enough for initialization to matter in the first place, it's going to be better.

Upvotes: 4

Related Questions