java - 如何使用 O(logN) 对具有 n 个元素的优先级队列进行排序？

Question

我有一个整数流，以及一个 int k，由用户提供。在程序结束时，我必须打印出 k 个最大的数字。我只允许使用容量为 k 的优先级队列。

我的问题是，当队列达到满容量时，下一个整数读取必须替换队列中最低的整数。

如何在插入后保持队列排序，以便我知道在下一次迭代中替换哪个 int，复杂度为 O(logn)？我使用 swim 方法(如下所示)，但是，虽然它将新的 int 放置在正确的级别，但它并没有使队列完全排序。

这是游泳方法:

private void swim(int i){
    while (i > 1) {  //if i root (i==1) return
        int p = i/2;  //find parent
        int result = cmp.compare(heap[i], heap[p]);  //compare parent with child
        if (result == 1) return;    //if child <= parent return
        swap(i, p);                 //else swap and i=p
        i = p;
    }
} 

为了让我自己更清楚，这里有一个 k = 3 的例子。

1: A = 42 / B = null / C = null

 2: A = 69 / B= 42 / C = null (69 swims upwards)

3: A = 69 / B= 42 / C = 32

 4: A = 69 / B= 42 / C = 32 (no change)

 5: A = 104 / B= 42 / C = 69 (104 is inserted replacing 32, then swims upwards)

 6: A = 104 / B= 42 / C = 93 (93 is inserted replacing 69, remains there)       

Answer 1

首先，你不能让PriorityQueue保持有序；它与堆数据结构相似，即使不完全相同。
PriorityQueue 只是根据它是最小堆或最大堆来授予顶部元素是最小堆或最大堆。

而且您还会对 排序元素 和查找 K 个最大/最小元素 这两个不同的问题感到困惑。

如果您想对给定的 N 元素列表中的元素进行排序:
使用基于比较的排序算法，您无法获得比 O(N*log(N)) 更好的运行时间。

但是，如果您的情况只是从 N 元素列表中查找 K 最小/最大元素:
您可以在 O(N*log(K)) 时间内实现。

请检查一次这个问题:Finding the first n largest elements in an array