java - 动态订单统计: get k-th element in constant time?

Question

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

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

我使用平衡的 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 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)) 时间)。另外，我不允许使用 HashMap 。

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

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-Tree 添加一个元素时，您都会计算出第 k (=n/a) 个最大元素(如您的代码中所做的那样)并存储它。这样，add() 函数仍然具有 O(log n) 运行时间。 get() 函数只是检索存储的值并且在 O(1) 中。