如何在 C++ 中处理堆
我知道这可能是“你只需尝试一下”类型的问题之一，但由于我还没有可用的实际测试数据，我想在我仍在设计代码时获得一些关于你的经验的意见。
我有一个数据结构，它实现了带有一些附加功能的优先级队列。我通常需要做的就是一次向这个堆中添加一堆对象。我使用 std::make_heap()、std::push_heap() 和 std::pop_heap() 算法来维护堆不变量。
现在，每当我进行插入时，我都会使用 std::push_heap() 来添加单个元素。现在我正在考虑使用 std::vector::push_back() 方法一次添加所有元素，然后重新组织堆。此时，简单的 push_heap() 可能无法工作，因此我必须使用新的 make_heap()。然而，make_heap()在(3*(last-first))中运行，而push_heap()只接受log(last-first) ）。
在这种情况下，是否有一种简单的方法可以确定哪一个实际上更快，或者我是否必须等到测试数据可用？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果将 k 个元素插入到大小为 n 的堆中，
make_heap()大约从 k⋅log 的点开始会更快2（n）> 3·n。这意味着当k > 时3·n / log2(n)。您可以在批量插入之前计算该值，然后决定哪种方法会更快。请注意，该值只是一个粗略的估计，因为该函数的实际实现可能不会完全这些时间来执行操作。但作为经验法则，它应该是有用的，并且可以获得相当好的结果。
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.
make_heap运行时不超过 3N 次比较（其中 N 是堆的大小），而push_heap不超过 log N。但是，您必须推送每个元素分别放入堆中，这意味着它需要 Npush_heaps，因此该方法受到 N log N 比较的限制。因此，
make_heap渐近优于 Npush_heap。如果堆足够大，初始化就很重要，那就更好了。make_heapruns with no more than 3N comparisons (where N is the size of the heap), whilepush_heaptakes no more than log N. However, you have to push each element into the heap separately, which means it takes Npush_heaps, so that method is bounded by N log N comparisons.Therefore,
make_heapis asymptotically better than Npush_heaps. If the heap is large enough for initialization to matter in the first place, it's going to be better.