哪种数据结构可以最快地找到最小值？

Question

需求是：

有一个仓库，这个仓库会有频繁的数值插入和删除。
每次插入或删除之后，都需要尽可能快地找到最小值。
其他值的定位速度不重要，也可以需要关心数值的排序。

目前我只能想到使用红黑树来实现。但红黑树应该说是面面俱到的一个数据结构，最小值和任何值的地位是一样的，存取速度的数学期望相同。

请问针对这样的一个需求，有没有比红黑树更合适、更快速的数据结构呢？

提前谢谢各位大神！！！

Answer 1

不是很懂，瞎写两句。
查了一下红黑树的增删查都是O(log n)的，而最小堆的增删是O(log n)，查最小值显然是常数时间。看起来对你的应用最小堆更好一点。

Answer 2

应该是红黑树吧。

以stl的红黑树为例，更新完再平衡一个节点最多不超过3次旋转，查最小值$O(1)$，具体参考stl代码。

再看最小堆，更新完再平衡需要$O(logn)$，要是n很大呢。

用红黑树好点，stl都实现好了，自己改下就行。而且你是频繁的数值插入和删除，红黑树最好。