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

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

此数据结构的要求如下：

1. 队列中的元素不一定是整数，但它们必须彼此比较，也就是说，当我们比较两个元素时，我们可以分辨出哪一个更大（它们也可以相等）。

2. 数据结构必须支持排队（在尾部添加元素）和取消排队（删除头部的元素）。

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

4. 您可以假设排队、取消排队和第 k 个最大元素查找的运算都以相同的频率发生。

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

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

Enqueue（x）：x首先插入到树中，假设相应的节点是节点_t，我们将对（x，指针到节点_t）附加到队列中。

取消排队：假设（e1，节点₁）是头部的元素，节点₁是指向对应于e1的树的指针。我们从树中删除节点₁，并从队列中删除（e1，节点₁）。

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

1. 如果 K< n_左，我们在 n_个根的左子树中找到第 K 个最大的元素;

2. 如果 K>n_根 n_右，我们在 n_个根的右子树中找到（K-n_根+n_右）第 1 个最大元素;

3. 否则 n_个根就是我们想要的节点。

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

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