我愿意使用数据结构作为恒定空间的溢出缓冲区.我想要有效的插入,但最重要的是有效地删除最小元素.我正在考虑使用堆,因为我有O(log(n))find_min()和log(n)插入和删除.另一方面,我知道与红黑树相比并不了解优势,因为它也有O(log(n))插入和删除,而O(1)找到最小/最大.而排序输出的优点(我不在乎).
问题涉及：Is a red-black tree my ideal data structure?
既然我有两个可用的std :: map和boost :: heap的结构,为什么我更喜欢使用堆而不是红黑树？
最后,使用红黑树,我也有一个入口的O(log(n))搜索时间,而对于堆,时间是O(n),这是重要的,因为存在重复.
解决方法
区别在于如何使用结构.
>二进制堆是用于插入值和检索最小值的非常快的数据结构.但是,它们不支持有效搜索或删除随机值.
>红/黑树是平衡的二叉搜索树,支持有效插入,删除,查找任意值,以及(合理快速)查找最小值.但是,与二进制堆相比,它们有很多开销.
如果你需要的是插入,find-minimum和remove-minimum,那么二进制堆可能是一个很好的选择,因为开销较低,运行时应该更快.如果您需要插入和删除任意值或查找任意值,则红/黑树可能是更好的选择.与所有工程一样,选择正确的数据结构都是关于权衡.
另外,请注意,如果需要二进制堆,可以使用std :: priority_queue;你不需要使用Boost.也不能保证std :: map是一个红色/黑色的树;它可能是某种平衡的BST,但它可以使用一些其他算法来平衡.
希望这可以帮助！
