c++ - 用于检索集合中第 k 个最小/最大项目的数据结构(在 STL 或 Boost 中)？

Question

我正在寻找具有以下属性的 C++ STL 或 boost 数据结构:

• 在 O(log n) 时间内检索第 k 个最大的项目
• 在 O(log n) 时间内搜索
• 在 O(log n) 时间内删除

如果不存在这样的数据结构实现，是否有办法用额外的数据(例如，集合)适应不同的数据结构，以便上述情况成为可能？

注意:我找到了is-there-any-data-structure-in-c-stl-for-performing-insertion-searching-and-r ，但这是 5 年前的事了，没有提到 boost。

Answer 1

目前我假设元素是唯一的并且至少有 k 个元素。如果没有，您可以类似地使用 multiset。

您可以在 C++ 中使用两个 set 来完成此操作:

#include <set>

第 1 组:我们称之为大。它只保留 k 个最大的元素。

第 2 组:我们称之为休息。它保留其余元素。

搜索:只搜索两个集合，需要 O(log n) 因为两个集合都是红黑树。

Deleting:如果元素在rest，直接删除即可。如果不是，则从large中删除，然后从rest中删除最大的元素，放入large中。从红黑树中删除需要 O(log n)。

插入新元素(初始化):每次来一个新元素:(1)如果large元素少于k个，将其添加到large 。 (2) 否则，如果元素大于 large 中的最小元素，则移除那个最小值并将其移动到rest。然后，将新元素添加到 large。如果以上都不是，只需将新元素添加到 rest。红黑树的删除和插入需要 O(log n)。

这样，large 总是有 k 个最大的元素，其中最小的元素就是您想要的第 k 个最大的元素。

我留给您来了解如何在集合中进行搜索、插入、求最小值、求最大值和删除操作。这并不难。但是所有这些操作在平衡二叉搜索树上都需要 O(log n)。