动态顺序统计：如何在常数时间内获取第k个元素？

Question

因此，我正在尝试实现一种数据结构来处理动态顺序统计。数据结构具有以下操作：

• add(x)：插入一个值为x的新元素
• get(k)：返回第k小的元素：其中k = ceiling(n/a)，其中n = 数据结构中的元素数量，a = 常量因子。
• reset：重置整个数据结构，即数据结构“为空”

我使用平衡的AVL树实现了我的数据结构。使用这个数据结构，操作的时间复杂度如下：

• add(x)：O(log(n))
• get(k)：O(log(n))

这是我用O(log(n))时间复杂度实现get(k)的代码：

public static int get(Node current, int k) {
    int l = tree.sizeLeft(current) + 1;
    if(k == l) {
        return current.value;
    } else if(k < l) {
        if(current.left == null) {
            return current.value;
        }
        return get(current.left, k);
    } else {
        if(current.right == null) {
            return current.value;
        }
        return get(current.right, k);
    }
}

这里是我为节点类编写的实现代码：

class Node {
int height, value, bal, size;   // bal = balanceFactor, size = amount of nodes in tree 
                                   rooted at current node
Node leftChild = null;
Node rightChild = null;

public Node(int val) {
    value = val;
    height = 1;
    size = 1; 
}

然而，我的任务是实现一个数据结构，可以处理上述操作，并且 仅在获取(k)操作时花费O(1)(常数)时间。(添加(x)仍需花费O(log(n))时间)。同时，我不允许使用哈希表。

有没有可能修改我的实现以获得恒定时间？ 或者，有哪种数据结构可以在恒定时间内处理获取(k)操作？

- G.M

---

@Turing85 这就是我为什么感到困惑的原因:/ - G.M

你确定这是常数时间吗？因为即使哈希映射也无法处理这个问题... 如果添加操作的时间复杂度是O(n)，我可以想到常数时间O(1)。 - Or251

你已经实现了解决这个问题的标准方法。我非常自信，你不能修改你正在使用的树算法，使get的时间复杂度为O(1)。除非add的时间复杂度为O(n)，否则我从未听说过动态顺序统计算法可以实现这一点。我的一个提醒是，除非编译器删除尾递归，否则你的get确实使用O(log n)空间。你可以使用循环重新实现它。然后它将在O(1) _空间_上运行。 - Gene

@Gene，请看一下我的回答。这不是一个 O(log a) = O(1) 的获取吗？ - גלעד ברקן

@Gene OP说a是一个常数，我们总是在寻找k = ceiling(n / a)。你的例子似乎是无效的。根据问题，k始终是ceiling(n / a)。 - גלעד ברקן

Answer 1

据我所知，k参数基本上随着元素的大小增长而增加，这意味着对于每个n，您都知道k的确切值。

如果是这种情况，那么我的建议是使用最大堆和最小堆。 最大堆将元素（小于等于第n/a个元素）组织成堆结构，允许在常数时间内访问最大元素（根）。 相应地，最小堆将元素（大于第n/a个元素）组织成堆结构，允许在常数时间内访问最小元素（根）。

当新元素到达（添加）时，您将它们放置在相应的堆中，在O(log n)时间内完成。如果最大堆变得比(n/a)更大或更小，则在两个堆之间重新平衡需要O(log n)时间。

现在，您的get()函数只需要以O(1)的时间返回最大堆的根元素即可。

在Java中，您可以使用优先队列作为最大堆（和最小堆）。

PriorityQueue<Integer> heap = new PriorityQueue<>(10, Collections.reverseOrder());

这段文本的英译中文为：

这个类可能看起来像这样

。

import java.util.Collections;
import java.util.PriorityQueue;

public class DOS
{

    double a;
    PriorityQueue<Integer> heap;
    PriorityQueue<Integer> heap_large_elements;

    public DOS(double a) {
        this.a = a;
        this.heap = new PriorityQueue<>(10, Collections.reverseOrder());
        this.heap_large_elements = new PriorityQueue<>();
    }

    public void add(int x){
        if(heap.size() == 0 || x < heap.peek())
            heap.add(x); // O(log n/a)
        else
            heap_large_elements.add(x); // O(log n)

        //possible rebalance operations
        int n = heap.size() + heap_large_elements.size();
        if(heap.size() > Math.ceil(n/a)){
            heap_large_elements.add(heap.poll()); //O(log n)
        }else if(heap.size() < Math.ceil(n/a)) {
            heap.add(heap_large_elements.poll()); //O(log n)
        }
    }

    public int get(){
        return heap.peek(); //O(1)
    }

    public static void main(String[] args)
    {
        DOS d = new DOS(3);
        d.add(5);d.add(6);d.add(2);d.add(3);d.add(8);d.add(12);d.add(9);
        System.out.println(d.get());
    }

}

编辑（由Cheaty McCheatFace编辑）：

另一个使用您的代码但有点作弊的想法是以下内容。每当您向AVL树添加一个元素时，计算k（=n/a）个最大元素（如您的代码中所做），并将其存储。这样，add（）函数仍具有O（log n）运行时间。 get（）函数只需检索存储的值即可在O（1）中完成。

- SaiBot

---

k是传递给get()的参数，也就是说，每次它都是不同的k。 - Matt Timmermans

这也是我最初的想法，但是“k = n/a，其中n = 数据结构中元素的数量，a = 常数因子”让我认为它取决于n。 - SaiBot

我不知道我是否做错了什么，但我已经实现并尝试了一个小例子：add(5)，add(6)，add(2) 和 factor a = 3，即 k = ceiling(3/3) = 1。那么当我调用 get() 时，它应该返回 2，是吗？因为我得到的是 6。 - G.M

很奇怪，插入所有元素后堆的大小是多少？您应该在每次插入后调用get()并检查结果。 - SaiBot

@G.M 更新了代码。现在使用了两个堆，可能需要在 add() 后重新平衡。希望我现在考虑到了所有情况 :) - SaiBot

Answer 2

如果您想使用树，维护1到最大平衡树之间的顺序a。对于每棵树，保持指向最小和最大元素以及树大小的指针。每当添加一个元素时，将其插入到适当的树中。如果一棵树增长超过ceiling(n / a)个元素，则通过将适当的最低或最高元素移动到相邻的树来重新组织树，以使它们的大小都在floor(n / a)和ceiling(n / a)之间。第k个元素将始终是其中一棵树的最小值或最大值。

Add需要O(log a + log(n/a) * a) = O(log n)时间。
Get需要O(log a) = O(1)时间。

- גלעד ברקן