支持快速查找第k大元素的队列数据结构

Question

21

我面临一个问题，需要支持快速查找第k大元素的队列数据结构。

该数据结构的要求如下：

enter image description here

我的想法是使用修改后的平衡二叉搜索树。该树与普通平衡二叉搜索树相同，只是每个节点i都附加了另一个字段n_i，其中n_i表示以节点i为根的子树中包含的节点数。支持以下操作：

为简单起见，假设所有元素都是不同的。

Enqueue(x)：将x首先插入到树中，假设对应的节点是节点t，我们将pair(x，指向节点t的指针)添加到队列中。

Dequeue：假设(e1，node₁)是队列头部的元素，node₁是对应于e1的指向树的指针。我们从树中删除node₁并从队列中删除(e1，node₁)。

查找第K大的元素：假设根节点是节点root，它的两个子节点是节点left和节点right（假设它们都存在），我们将K与n_root进行比较，可能会出现三种情况：

所有这三个操作的时间复杂度均为O(log_N),其中N是当前队列中的元素数量。

如何加速上述操作？使用什么数据结构以及如何使用？

- outlaw

1

这似乎是一个人为制造的容器（查找第k个元素，但不删除它，所有操作都具有相等的频率）-您能否提供有关您要解决的根本问题的更多信息？如果您确实需要所有这些要求，我认为您已经找到了一个可靠的解决方案。 - Mark B

这可能需要一些时间来阅读，但是boost::multiIndex可以帮助解决这个问题。 - andre

@smocking，enqueue和dequeue操作必须按顺序（FIFO）进行，对元素访问没有其他限制。 - outlaw

1

@outlaw，谢谢。我认为我同意Mark B的观点。如果k是常数（实际上不是），你可以使用堆来跟踪第k个元素。这将允许O(1)查找第k个元素和O(logN)进行入队/出队操作。 - smocking

2

将二叉搜索树和队列合并为一个结构是值得的。只需为每个节点使用一个额外的指针，该指针应指向FIFO顺序中的下一个节点。 - Evgeny Kluev

显示剩余11条评论

3个回答

2

我找到了一篇有趣的论文：

《VLDB 2008 上发表的关于不确定流上滑动窗口 Top-k 查询的论文》，已被引用71次。

VLDB是数据库研究领域最好的会议，引用数量证明了数据结构确实有效。这篇论文看起来很难，但如果你真的需要改进你的数据结构，我建议你阅读这篇论文或者参考页中的其他论文。

- Heejin

1

您还可以使用指数树。

例如，可以通过在树中将内部节点标记为其子节点的最小优先级来实现优先队列，或者可以通过将节点标记为其子节点中叶子节点的计数来实现索引列表/数组。指数树可以提供摊销O(1) cons、reversing、cdr、O(log n) append和split；并且可以适应于索引或有序序列。

此外，请注意，作为纯函数结构使其成为并发使用的良好选择。

- Dilum Ranatunga

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

注意 - 你不能在所有情况下都达到比 O(logn) 更好的效果，最好的情况是你需要“选择”最关心的操作。（否则，你可以通过将数组提供给 DS 并查询第1个、第2个、第3个... 第n个元素，在 O(n) 中进行排序。）

使用跳表而不是平衡二叉搜索树作为排序结构可以将出队复杂度降至O(1)平均情况。它不会影响其他操作的复杂度。
从跳表中删除元素 - 你只需要使用指向队列头部的指针到达元素，然后沿着链接删除每个元素。期望需要删除的节点数为1 + 1/2 + 1/4 + ... = 2。
查找第K个元素可以在O(logK)时间内完成，从最左边的节点（而不是根节点）开始，并向上移动直到发现"超过所需儿子数量"，然后像问题中的算法一样将刚刚找到的节点视为根节点。虽然渐进复杂度更好，但常数因子加倍。