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

Question

所以，我正在尝试实现一个数据结构来处理动态订单统计。数据结构有以下操作：

add(x): 插入一个值为 x
get(k): returns 第 k 个最小元素：k = ceiling(n/a)，其中 n = 数据结构中元素的数量，a = 常数因子。
重置：重置整个数据结构，即数据结构“在它之后为空

我使用平衡 AVL 树实现了我的数据结构。使用此操作具有以下时间复杂度：

添加(x): O(log(n))
得到（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:

的实现

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; 
}

}

然而，我的任务是实现一个可以处理上述操作的数据结构，并且操作get(k)只需要O(1)（常数）时间。（并且 add(x) 仍然需要 O(log(n)) 时间）。另外，我不允许使用哈希图。

是否可以修改我的实现以获得恒定时间？或者，什么样的数据结构可以在恒定时间内处理 get(k) 操作？

Answer 1

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

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

当新元素到达（添加）时，您将它们放置在 O(log n) 的相应堆中。如果最大堆变得大于或小于 (n/a)，则在 O(log n)

中重新平衡两个堆

您的 get() 函数现在只需要 return O(1) 中最大堆的根元素。

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

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

class 可能看起来像这样

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) 中。

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) 时间。

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

Dynamic order statistic: get k-th element in constant time?

java

algorithm

data-structures

binary-search-tree

avl-tree