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

Question

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

抬头看。如果我插入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++ 进行编码。

Answer 1

我相信这样的数据结构不存在。对任何元素的持续查找(例如索引)需要连续的内存，如果您想保持范围排序，这使得插入不可能在小于 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 混淆。}