具有排序的快速插入/删除数据结构

Question

我急需一种数据结构，可以进行大量插入和删除（数量可能相当），并且可以非常快速地查找最高（或最低）值。删除操作总是只影响最高（或最低）值。问题在于这些值必须被排序，并且在任何时刻我都可以插入一个元素到其他两个元素之间的任意位置。我想要快速读取（和删除）的唯一值是最大值（或最小值）。请问你有什么建议吗？请对您提出的答案进行算法复杂度分析。

- em70

---

请澄清您的问题和评论。您说最大插入，但似乎您只需要插入。此外，您说值必须排序，但又说您只需要读取最大值。最后，O(log n)非常接近于O(1)，但您似乎想要更快的速度。您实际要执行多少操作？ - flight

操作应该在每秒2百万次左右。绝大部分将是最大插入，而相对较小的百分比（<30％）将是在任意位置插入。至于排序，如果放弃它可以提高其他操作的算法复杂度，我并不太在意（请参见下面关于我的配对堆计划使用的评论）。 - em70

Answer 1

看起来你需要一个最大堆。

支持O(log n)插入，O(1)查找最大值和O(log n)删除最大值。

- Aryabhatta

---

虽然+1是可以的，但最好能够实现O(1)的最大插入和删除，因为这将是执行次数最多的操作之一，除了查找以外。 - em70

@emaster：你所说的“max insertion”是什么意思？难道不只是插入吗？如果你插入最大值，那在堆中它将是O(1)。如果你只是指插入，那么你可以使用你的结构在线性时间内对n个数字进行排序。如果你只使用比较，那么排序的下限是Omega(nlogn)... - Aryabhatta

@emaster70：在具有高分支因子的堆中，O(log n)非常接近于O(1)。或者像Jim Mischel的回答中建议的那样使用斐波那契堆。 - Conrad Meyer

Answer 2

一个堆是您想要的。这是一个简单的二叉堆实现。它是最大堆还是最小堆取决于您传递给它的比较函数：http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=789 请注意，二叉堆不是构建堆的唯一方法。但它可能是最容易构建的，并且在大多数情况下表现良好。

堆中的项目未排序，尽管它们已排序。唯一的保证是最高（最低）的项目位于堆的顶部，并且将在您询问下一个项目时检索到该项目。

您正在构建的内容听起来像是一个优先队列。有其他实现优先队列的方法。例如，我看到过基于跳表的优先队列优于基于堆的优先队列。

如果确实需要O(1)插入，则可以查看Fibonacci堆之类的东西。

- Jim Mischel

---

斐波那契堆主要用于计算机科学理论领域，以达到最佳的渐进运行时间。常数较大，建议使用配对堆或其他数据结构代替。 - user635541

鉴于我的问题性质，如果我能够开发出一个良好的实现，无论是斐波那契堆还是 - 如用户635541所建议的 - 配对堆都应该可以胜任，因为它们似乎是我可以根据操作类型的平均频率分布最接近我的需求的选择。 - em70

Answer 3

这种数据结构被称为自平衡二叉搜索树，在我使用的每种语言中都有实现，除了Borland Pascal。
你提到的所有操作（添加/删除/查找）的成本都是O(logn)。最小-最大查找也可以是O(1)。

你可以按排序顺序遍历所有元素，时间复杂度为O(n)。

编辑
我不建议使用堆，因为它不能满足“必须排序”的要求。

如果你只需要插入/删除/查找最大值，那么我建议使用排序数组或链表。最大插入/删除/查找O(1)，并且所有元素已经排序。

- Nikita Rybak

---

+1 但是与上面相同，O(log n) 对于最大插入和删除似乎不够好 :( - em70

在O(1)中进行最小值-最大值查找？我认为你需要做一些调整..（在AVL、RB-Tree等数据结构中），例如让一个节点指向Min / Max，.. - Oscar Mederos

对于最大插入/删除，简单数组应该可行 :) - Nikita Rybak

@OscarMederos 嗯，存储指向最大值的指针不会影响复杂度。 - Nikita Rybak