Geek asks and answers

How to handle heaps in C ++

I know this is probably one of those questions that you just need to try, "but since I don't have any test data yet, I would like to get some input into your experience while I'm still designing the code.

I have a data structure that implements a priority queue with some added features. Usually I need to add a bunch of objects to this bunch at a time. I use algorithms std::make_heap(), std::push_heap()and std::pop_heap()to preserve heap invariants.

Now, when I do the insertion, I use std::push_heap()to add one element. Now I'm thinking of adding all the elements at a time using the method std::vector::push_back()and then reorganizing the heap. Downtime push_heap()at this time probably won’t work, so I’ll have to use a new one make_heap(). However, it make_heap()works in (3*(last-first)), but push_heap()accepts only log(last-first).

Is there an easy way to find out which one is actually faster in this case, or do I need to wait for the test data to be received?

+3
source share
2 answers

If you insert k elements into a heap of size n, it make_heap()will be faster roughly from the point where k & sdot; log 2(n)> 3 & SDOT; n. This means when k> 3 & sdot; n / log 2 (n). , , .

, , , , . , , .

+4

make_heap 3N ( N - ), push_heap , log N. , N push_heap s, N log N.

, make_heap N push_heap s. , .

+4

More articles:


All Articles