2

我正在研究 c++ stl 算法并试图理解堆算法（make_heap、sort_heap、push_heap 等）。我了解它创建的二叉树，以及这对于在任何给定时间有效地找到最高优先级的项目有何用处。我不清楚这比维护一个排序的容器更好，在这个容器中，价值最高的项目可以简单地从顶部弹出。

这是我所看到的比较：

对于堆：

  • 创建堆： make_heap: O(nlogn) ...错误！上）
  • 插入：push_heap：O(logn)
  • 删除最高：pop_heap: O(logn)
  • 获取排序列表：sort_heap: O(nlogn)

对于已排序的容器：

  • 初始排序：sort() O(nlogn)
  • 插入： ? O（登录）
  • 移除最高：pop常量
  • 获取排序列表：已经排序的常量

插入需要找到具有相同值的元素或值两侧的两个元素。在排序列表中，这应该是 O(logn)。我还不知道可以做到这一点的特定算法。

无论如何，我错过了什么？从我上面的分析看来，仅仅维护一个排序的容器在所有情况下都不会更糟，在某些情况下会更好。

谢谢！

编辑：

我想指出这一点，所以没有人会读到这篇文章并对我的问题感到困惑。正如 rici 指出的那样，我误解了 make_heap 的复杂性。我最初以为是 O(n log n)，但实际上是 O(n)。对我来说，这种差异解释了为什么 make_heap 比简单地维护一个排序列表更好。

4

3 回答 3

3

make_heap 是O(n)，不是O(n log n)。对于大型数据集，它可能比排序快得多。

操作（push 和remove_min O(log n)）可能只比平衡二叉树实现快一点，但它们的存储开销要低得多，这也提高了它们的缓存友好性。对于像整数这样的小对象，堆使用的内存大约是 std::set 使用的内存的四分之一。

于 2013-10-31T04:50:28.470 回答
2

排序列表的插入不是O(log n)，这是最坏的情况O(n)，因为您必须移动数组中的元素。

于 2013-10-31T05:40:03.557 回答
1
  1. 您可能不想要整个排序序列。
  2. 您可能希望快速获取第一个项目，并在所有检索条目中分散计算负载以进行排序，而不是预先支付所有费用。
  3. 您可能想要处理大于内存容量的集合。一个堆可以产生其自身大小平均为 2N 的排序运行。这种技术用于排序合并程序，当初始运行的数量支配每次运行的排序时间时。

在这些情况下，堆获胜。

于 2013-10-31T04:42:45.880 回答