如何在C++中处理堆(heap)

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)。

在这种情况下，是否有一种简单的方法来确定哪个实际上更快，还是说我必须等待测试数据出现？

- LiKao

Answer 1

make_heap最多需要3N次比较（其中N为堆的大小），而push_heap最多需要log N次比较。然而，您必须将每个元素逐个推入堆中，这意味着它需要N个push_heap，因此该方法受N log N次比较的限制。

因此，make_heap在渐进意义下优于N个push_heap。如果堆足够大以至于初始化在第一次使用时很重要，那么使用make_heap会更好。

- David Thornley

---

假设队列一开始是空的。 - Steve Jessop

Answer 2

如果您将k个元素插入大小为n的堆中，make_heap()函数在k⋅log₂(n) > 3⋅n的点处速度会更快。这意味着当k > 3⋅n / log₂(n)时，该方法将更快。您可以在大规模插入之前计算此值，然后决定哪种方法更快。

请注意，这个值只是一个粗略估计，因为实际实现可能不会完全按照这些时间执行操作。但它应该作为经验法则有用，并且能够得到合理的结果。

- sth