algorithm - 哪种数据结构可以处理这些需求？

Question

我需要一个可以处理这些需求的数据结构: * 在 O(lg(n)) 中检索最小值 * 在 O(lg(n)) 中检索最大值 * 向数据结构中插入一个值 O(lg(n))

对于 max 和 insert - 我认为最大二叉堆可以处理这个问题，但是它不适用于 min，因为最小值可以在每个大约 n/2 值的叶子中 - 换句话说 O (n) ？如果我错了，请告诉我。

另外，如果有人能帮助我找到满足这些需求所需的数据结构，我将非常高兴。

非常感谢

Answer 1

Min-max heap正是您要找的。