algorithm - 具有快速排序插入、排序删除和查找的数据结构

我正在寻找一个非常具体的数据结构。假设元素的最大数量是已知的。所有元素都是整数。允许重复。操作是：

抬头。如果我插入n个元素，a[0]是最小的元素，a[a.length - 1]是最高的。a[k]是第 k 个最小元素。所需的运行时间：O(1)

插入。进行排序插入，insert(b)其中b是一个整数。所需的运行时间：O(log n)

删除。delete(i)删除第 i 个元素。所需的运行时间：O(log n)

我想要什么样的数据结构是这样的？我的问题与语言无关，但我使用 C++ 进行编码。

标签： algorithmsortingdata-structures

我相信这样的数据结构不存在。对任何元素（例如索引）的持续查找需要连续的内存，这使得插入不可能在少于O(n)你想要保持范围排序的情况下进行。

哈希表和围绕哈希表的包装器存在争议，但在提及它们时需要牢记两点：

哈希表在中具有平均访问（插入、删除、查找）O(1)，但假设很少有哈希冲突。如果您希望满足有关悲观复杂性的要求，哈希表是不可能的，因为它们的悲观访问时间是O(n).
哈希表本质上是无序的。大多数时候，它们确实有用于存储（例如）数据桶的内部数组，但元素本身既不是全部在连续内存中，也不是按某些属性排序（除了可能是它们的哈希模数，它本身应该产生非常相似对象的不同值）。

为了不让您空手而归 - 如果您希望尽可能接近您的要求，您需要指定您会牺牲哪些复杂性来实现其他复杂性。我想提议std::priority_queue或std::multiset。

std::priority_queue仅提供对顶部元素的访问 - 保证它将是集合中的最小或最大（取决于您用于指定关系的比较器）元素。插入和删除都是O(log_n)及时实现的。
std::multiset* 提供对其中每个元素的访问，但成本更高 - O(log_n). 它还实现O(log_n)了插入和删除。

*_{小心 - 不要与std::set不允许重复元素的混淆。}