data-structures - 有效的数据结构，返回大于或等于给定键的最小元素并允许减少键

Question

是否存在允许以下操作的高效（log n）数据结构：

• 返回大于或等于给定键的最小元素
• 将此元素与较小的元素交换并相应地重新排列结构

元素的数量是已知的，并且在生命周期内不会改变。

Answer 1

你可以实现一个平衡的二叉树，比如红黑树

红黑树的搜索、插入和删除时间复杂度为 O(log(n))。

您必须进行一些修改以返回大于或等于给定键的最小元素。但我猜这个数据结构提供了基本行为。