我愿意使用数据结构作为常量空间的溢出缓冲区。我想要有效地插入，但最重要的是有效地删除 min 元素。我正在考虑使用堆，因为我有 O(log(n)) find_min() 和 log(n) 插入和删除。另一方面，我不明白与红黑树相比的优势，因为它也有 O(log(n)) 插入和删除，但 O(1) 找到最小值/最大值。以及排序输出的优势（我不在乎）。
问题涉及：红黑树是我理想的数据结构吗？
既然我可以从 std::map 和 boost::heap 获得两种结构，为什么我应该更喜欢使用堆而不是红黑树？最后，使用红黑树，我还有 O(log(n)) 搜索条目的时间，而对于堆，时间是 O(n)，这很重要，因为存在重复项。
区别主要在于您将如何使用这些结构。
二进制堆是用于插入值和检索最小值的非常快速的数据结构。但是，它们不支持有效搜索或删除随机值。
红/黑树是平衡的二叉搜索树，支持高效的插入、删除、任意值的查找和（相当快的）查找最小值。但是，与二进制堆相比，它们有很多开销。
如果您只需要插入、查找最小值和删除最小值，那么二进制堆可能是一个更好的选择，因为开销较低并且运行时应该更快。如果您需要插入和删除任意值或查找任意值，红/黑树可能是更好的选择。与所有工程一样，选择正确的数据结构就是权衡取舍。
另外，请注意，std::priority_queue如果您需要二进制堆，则可以使用；你不需要使用Boost。也不能保证std::map是红/黑树；它可能是某种平衡的 BST，但可以使用其他算法来平衡。
希望这可以帮助！
堆很容易在连续内存中实现，即数组。红黑树通常是为每个节点分配一个单独的堆来构造的。红黑树最终会在每次树遍历时访问整个堆的内存。这是最坏情况下的缓存行为。尽管两种结构的某些操作的算法复杂度相同，但红黑树的恒定开销要高得多。