21

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

该数据结构的要求如下：

  1. 队列中的元素不一定是整数，但它们必须是相互可比的，即我们可以通过比较两个元素来判断哪个更大（它们也可以相等）。

  2. 数据结构必须支持入队（添加尾部元素）和出队（删除头部元素）。

  3. 它可以快速找到队列中第 k 个最大的元素，请注意 k 不是常数。

  4. 您可以假设操作 enqueue 、 dequeue 和第 k 个最大元素查找都以相同的频率发生。

在此处输入图像描述

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

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

Enqueue(x)：首先将 x 插入树中，假设对应的节点是节点t，我们将 pair(x,pointer to node t ) 附加到队列中。

出队：假设（e1，节点1）是头部的元素，节点1是指向与e1对应的树的指针。我们从树中删除节点1并从队列中删除 (e1, node 1 )。

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

  1. 如果 K< n left我们在 n root的左子树中找到第 K 个最大的元素；

  2. 如果 K>n root -n right我们在 n root的右子树中找到 (Kn root +n right )-th 最大的元素；

  3. 否则 n root是我们想要的节点。

所有三个操作的时间复杂度都是 O(log N ) ，其中 N 是当前队列中的元素数。

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

4

3 回答 3

9

注意 - 你不可能比O(logn)所有人都做得更好，充其量你需要“选择”你最关心的操作。（否则，您可以O(n)通过将数组提供给 DS 并查询第一个、第二个、第三个、...第 n 个元素来进行排序）

  • 使用跳过列表而不是平衡 BST 作为排序结构可以将出队复杂度降低到O(1) 平均情况。它不会影响任何其他操作的复杂性。
    要从跳过列表中删除 - 您需要做的就是使用队列头部的指针到达元素，然后沿着链接向上并删除每个链接。需要删除的预期节点数为 1 + 1/2 + 1/4 + ... = 2。
  • find Kth 可以O(logK)通过从最左边的节点（而不是根节点）开始并一直向上直到您发现“需要更多的儿子”来实现，然后将刚刚找到的节点视为根节点，就像算法一样这个问题。虽然它在渐近复杂性方面更好 - 常数因子是两倍。
于 2012-09-21T15:21:06.117 回答
2

我发现了一篇有趣的论文：

Sliding-Window Top-k Queries on Uncertain Streams 发表于 VLDB 2008 并被 71 引用。

https://www.cse.ust.hk/~yike/wtopk.pdf

VLDB是数据库研究领域最好的会议，引用次数证明数据结构确实有效。

这篇论文看起来很难，但是如果你真的需要改进你的数据结构，我建议你阅读这篇论文或者这篇论文参考页面中的论文。

于 2012-09-21T15:29:44.037 回答
1

您也可以使用手指树。

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

另请注意，作为纯粹的功能结构，这使其成为并发使用的不错选择。

于 2012-09-27T04:55:07.000 回答