对于我的用例，是否有比最小堆更快的东西？
我的用例如下：
- 我需要获得一组不断增长的元素中的最小值；我只需要任何迭代的最小值
- 我将更新最小值，之后它保证不再是最小值，但它在订单中的新位置通常不能直接计算。
- 我将这个新值推回到集合中，然后转到下一次迭代，在那里我查看新的 min 元素。
现在我正在以下列方式使用 std::vector 和 std::pop_heap std::push_heap 。我在向量上调用 std::pop_heap 将最小元素推到向量的后面，我得到最后一个元素的引用并更新它，然后我调用 std::push_heap 将最后一个元素移动到它的新位置. 所以我不必从 std::vector 复制结构体来更新它。有问题的结构是 16 个字节，并且可以简单地构造，它的基本结构完全由整数类型组成。
根据我的分析器和一系列问题大小，我看到的是我在 std::pop_heap 上花费了超过 75% 的 CPU 时间，在 std::push_heap 上花费了大约 10%。现在，在每个被检查的最小元素上执行的逻辑非常简单，主要包括添加和与固定输入的一些比较，所以我认为这可能和它一样好。但是，如果有一个不同的或随机的奇怪数据结构可能比我目前使用的 min_heap 更快，那么尝试一下会很有趣。
我已经尝试过 std::min_element、std::nth_element、std::sort，对于 1,000,000 或更少的问题大小，每一个都需要我当前的解决时间不到 1 秒，并将运行时间增加几个数量级（许多10 秒）。鉴于它们都具有比 std::push_heap 和 std::pop_heap 更糟糕的复杂性，我会期待这一点。
我也尝试过使用像 std::map 和 std::set 这样的树结构，但这些也会降低性能（我现在手头没有数字）。
那么对于这个用例，有人知道比 min_heap 更好的东西吗？
（不幸的是，我无法提供源代码，但鉴于 85% 的 CPU 时间都花在 pop_heap/push_heap 上，我认为无论如何它都不会非常有用）
编辑：比较运算符是两个整数类型之间的单个比较。所以它不像堆中使用的比较运算符正在做大量的工作。
回答
与其删除最小元素并重新插入更新的值，您还可以就地更改值并从根开始向下冒泡。删除最小元素通常会用最糟糕的元素之一替换它来替换根，通常会花费较长的向下气泡，然后重新插入相对较小的值也会花费相对较长的向上气泡。就地更改密钥仅用一个向下气泡代替了这两个组合，只要新值保持相对接近根的平均值，该气泡通常也更短。
遗憾的是，在 中没有此功能<algorithm>，但推出自己的功能并不太难。通过制作根的临时副本，而不是一系列s ，将其写成移动到一个“洞”留下的“洞” std::swap。用交换来做它可以使加载和存储的总数增加一倍。
使用一大堆更大的数量（可能是 4 个，也可能是 8 个）可能会有所帮助。