如何使用 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

您可以将数据排列在二叉树中，并通过二叉树搜索找到您要删除某些内容的最小编号。二叉树搜索的复杂度为 O(log N)，插入一个元素也具有 O(log N) 的复杂度。

现在谈论你对长度为 k 的队列的约束，你可以转换二叉树并将其存储在长度为 k 的数组中。

您可以查看此 link If I store a binary tree in an array, how do I avoid the wasted space? 以了解如何在数组中实现二叉树。

Answer 2

连你的评论In step 5, 104 and 69 switch places和so that after each iteration, the lowest element is at C都不一致。因为在第 5 步中，最低值 42 位于 B.

也许您正在寻找与此类似的解决方案。

public class FixedCapacityPriorityQueue {

    static class MyPriorityQueue extends PriorityQueue<Integer> {

        private final int capacity;

        public MyPriorityQueue(int capacity) {
            super(capacity, Comparator.reverseOrder());
            this.capacity = capacity;
        }

        @Override
        public boolean add(Integer i) {
            super.add(i);
            if (size() > capacity) {
                Integer lowest = Integer.MAX_VALUE;
                for (Integer next : this) {
                    if (lowest.compareTo(next) > 0) {
                        lowest = next;
                    }
                }
                this.remove(lowest);
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Integer[] stream = {42, 69, 32, 5, 104, 93};

        for (int i = 0; i < stream.length; i++) {
            PriorityQueue queue = new MyPriorityQueue(3);
            System.out.print("added to queue   : ");
            for (int e = 0; e <= i; e++) {
                 System.out.printf("%d ", stream[e]);
                queue.add(stream[e]);
            }
             System.out.println();
            System.out.print("elements in queue: ");
            while (queue.size() > 0) {
                System.out.printf("%d ", queue.poll());
            }
            System.out.printf("%n%n");
        }
    }
}

输出

added to queue   : 42 
elements in queue: 42 

added to queue   : 42 69 
elements in queue: 69 42 

added to queue   : 42 69 32 
elements in queue: 69 42 32 

added to queue   : 42 69 32 5 
elements in queue: 69 42 32 

added to queue   : 42 69 32 5 104 
elements in queue: 104 69 42 

added to queue   : 42 69 32 5 104 93 
elements in queue: 104 93 69

Answer 3

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

而且您对 排序元素 和 查找 K max/min 个元素 这两个不同的问题感到困惑。

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

但是，如果您的情况只是 从 N 个元素的列表中找到 K min/max 个元素：
您可以在 O(N*log(K)) 时间内完成。

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

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

How to sort with O(logN) a priority queue with n-elements?

java

heap

tree

priority-queue