动态订单统计:在恒定时间内得到第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; 
}

}

但是,我的任务是实现一个可以处理上述操作的数据结构,并且只对操作get(k)采用O(1)(常数)时间.(并添加(x)仍然采用O(log(n))时间).另外,我不允许使用hashmap.

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

Answer 1

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

如果是这种情况，那么我的建议是使用最大堆和最小堆。最大堆将元素（小于第 n 个元素）组织在堆结构中，允许在恒定时间内访问最大元素（根）。因此，最小堆在堆结构中组织元素（大于第 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)。