如何使用 PriorityQueue 集合从 java 中的给定数组在 O(n) 时间内构建最大堆？

Question

我试图在给定的大小为 n 的数组中找到第 K 个最大的元素。我的想法：从给定的数组构建一个最大堆（这需要 O(n) 时间）。然后从最大堆中移除 (k-1) 个元素。最后 return 堆中最顶层的元素。

我知道我可以通过从数组中一个接一个地取出元素来构建堆，但这需要 O(nlogn) 的时间来构建堆。

 public int findKthLargest(int[] nums, int k) {
       
        //max heap
        PriorityQueue<Integer> pq;
       // pq = how to build pq from nums in O(n) time??
        
        while(k>1){
            pq.poll();
        }
        
        return pq.peek();
    }

如何在 O(n) 时间内构建 maxheap？

Answer 1

1) 如何使用 Java 的 PriorityQueue 在 O(n) 中构建 MinHeap？

您应该使用 Collection 构建 PriorityQueue 而不是使用一对一的方法。使用 Arrays 包将数组转换为 List.

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(nums));

它利用基于 sink 的方法创建时间复杂度为 O(n) 的 pq。虽然不一样，但是用数组创建pq可以这样实现：

 public MinPQ(int[] keys) {
   n = keys.length;
   pq = new int[keys.length + 1];
   for (int i = 0; i < n; i++)
        pq[i+1] = keys[i];
   for (int k = n/2; k >= 1; k--)
        sink(k);
    }

private void sink(int k) {
   while (2*k <= n) {
      int j = 2*k;
      if (j < n && pq[j] > pq[j + 1]) j++;
      if (pq[k] <= pq[j]) break;
      exch(k, j);
      k = j;
    }
  }
private void exch(int i, int j) {
    int swap = pq[i];
    pq[i] = pq[j];
    pq[j] = swap;
}

这只是一个示例，展示了如何针对 O(n) 时间复杂度实现构造函数。你不需要实现它们，它们已经在 PQ 中实现了。

2) 如何使用 Java 的 PriorityQueue 在 O(n) 中构建 MaxHeap？

很遗憾，您不能同时将 Comparator 和 Collection 传递给 Java 的 PQ。您可以做的是编写您自己的 PQ，它扩展了 Java 的 PQ（大多数方法将保持不变）。可以找到一个漂亮的实现。
下面的实现使用了以下事实：

public PriorityQueue(PriorityQueue<? extends E> c)
Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue.

感谢@samabcde：

import java.util.*;

public class CustomComparatorPriorityQueue<T> extends PriorityQueue<T> {
    private Collection<T> wrapped;

    public static <U> PriorityQueue<U> create(Collection<U> wrapped, Comparator<U> custom) {
        return new PriorityQueue<U>(new CustomComparatorPriorityQueue<>(wrapped, custom));
    }

    private CustomComparatorPriorityQueue(Collection<T> wrapped, Comparator<T> custom) {
        super(custom);
        this.wrapped = wrapped;
    }

    @Override
    public Object[] toArray() {
        return wrapped.toArray();
    }

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(3, 6, 4, 8, 1, 9);
        PriorityQueue<Integer> pq = CustomComparatorPriorityQueue.create(a, Comparator.<Integer>naturalOrder().reversed());
        Integer b;
        while ((b = pq.poll()) != null) {
            System.out.println(b);
        }
    }

}

Java的PQ相关构造函数：

public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
        this.queue = ensureNonEmpty(c.toArray());
        this.size = c.size();
    } else {
        initFromCollection(c);
    }
}

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
 }

/**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 * This classic algorithm due to Floyd (1964) is known to be O(size).
 */
private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;
    final Comparator<? super E> cmp;
    if ((cmp = comparator) == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}

结论

简而言之，您可以使用一行代码在 O(n) 中创建 MinHeap，要在 O(n) 中创建 MaxHeap，您应该从头开始实现自己的 MaxHeap 或实现一个利用属性的 PriorityQueue(PriorityQueue<? extends E> c)，上面提到的

如何使用 PriorityQueue 集合从 java 中的给定数组在 O(n) 时间内构建最大堆？

How to build max heap in O(n) time from a given array in java by using PriorityQueue collection?

java

collections

priority-queue

time-complexity

max-heap

1) 如何使用 Java 的 PriorityQueue 在 O(n) 中构建 MinHeap？

2) 如何使用 Java 的 PriorityQueue 在 O(n) 中构建 MaxHeap？

结论