c++ - 如何在 C++ 中处理堆

Question

我知道这可能是“你只需要尝试一下”这类问题之一，但由于我还没有实际的测试数据，我想在我还在的时候就你的经验征求一些意见设计代码。

我有一个数据结构，它实现了一个带有一些附加功能的优先级队列。我通常需要做的是一次向这个堆中添加一堆对象。我正在使用 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 )。

在这种情况下，是否有一种简单的方法可以确定哪个实际上更快，还是我必须等到测试数据可用？

Answer 1

如果您将 k 个元素插入到一个大小为 n 的堆中，make_heap() 将大致从 的点开始更快k⋅log₂(n) > 3⋅n。这意味着当 k > 3⋅n/log₂(n) 时。您可以在大量插入之前计算该值，然后决定哪种方法会更快。

请注意，此值只是粗略估计，因为函数的实际实现可能不会正好这些时间来执行操作。但作为经验法则，它应该是有用的，并且会获得相当好的结果。