队列数据结构支持快速第k个最大元素发现

Question

我遇到了一个需要Queue数据结构支持快速第k个最大元素查找的问题.

该数据结构的要求如下:

1. 队列中的元素不一定是整数,但它们必须相互比较,即当我们比较两个元素时它们可以分辨哪一个更大(它们也可以相等).

2. 数据结构必须支持入队(在尾部添加元素)和出列(删除头部的元素).

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

4. 您可以假设操作入队,出列和第k个最大元素查找都以相同的频率发生.

我的想法是使用修改后的平衡二叉搜索树.该树与普通平衡二叉搜索树相同,除了每个节点_i用另一个字段n _i增强,n _i表示包含在具有根节点_i的子树中的节点的数量.上述操作支持如下:

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

Enqueue(x):首先将x插入树中,假设相应的节点是节点_t,我们将对(x,指向节点_t的指针)附加到队列.

出队:假设(e1,节点₁)是头部的元素,节点₁是指向对应于e1的树的指针.我们从树中删除节点₁并从队列中删除(e1,节点₁).

第K个最大元素发现:假设根节点是节点_根,它的两个子节点是节点_左边和节点_右边(假设它们都存在),我们将K与n _根比较,可能发生三种情况:

1. 如果满足K <N _左我们发现在n的左子树的第K个最大元素_根 ;

2. 如果K> n _root -n _right,我们在n _root的右子树中找到(Kn _root + n _right)第n 个最大元素;

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

所有三个操作的时间复杂度为O(log _N),其中N是当前队列中的元素数.

如何加快上述操作？什么数据结构和如何？

Answer 1

注意 - 你无法取得更好的成绩O(logn),最多你需要"选择"你最关心的操作.(否则,你可以O(n)通过将数组馈送到DS,并查询第1,第2,第3,......第n个元素来排序)

• 使用跳过列表而不是平衡BST作为排序结构可以将出列复杂度降低到O(1) 平均值.它不会影响任何其他操作的复杂性.
  要从跳过列表中删除 - 您需要做的就是使用队列头部的指针到达元素,然后按照链接并删除每个链接.需要删除的预期节点数是1 + 1/2 + 1/4 + ... = 2.
• 找到Kth可以O(logK)通过从leftest节点(而不是根)开始实现,直到找到"需要更多儿子"为止,然后将刚找到的节点视为根,就像算法一样.这个问题.虽然渐近复杂度更好 - 常数因子是双倍的.