java - java - 如何使用PriorityQueue集合从Java中的给定数组在O(n)时间内构建最大堆?
问题描述
我试图在给定的大小为 n 的数组中找到第 K 个最大的元素。我的想法:从给定的数组构建一个 maxheap(这需要 O(n) 时间)。然后从 maxheap 中删除 (k-1) 个元素。最后返回堆中最顶层的元素。
我知道我可以通过从数组中一个一个地获取元素来构建堆,但这需要 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?
解决方案
1) 如何使用 Java 的 PriorityQueue 在 O(n) 中构建 MinHeap?
您应该PriorityQueue
使用一个Collection
而不是使用一个接一个的方法来构建。使用Arrays
package 将您的数组转换为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?
好吧,不幸的是,您不能同时将 aComparator
和 a传递Collection
给 Java 的 PQ。您可以做的是编写自己的 PQ 来扩展 Java 的 PQ(大多数方法将保持不变)。一个漂亮的实现可以在这里找到。
下面的实现使用了以下事实:
public PriorityQueue(PriorityQueue<? extends E> c)
创建一个包含指定优先级队列中元素的 PriorityQueue。此优先级队列将按照与给定优先级队列相同的顺序进行排序。
感谢@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)
。
推荐阅读
- c# - 外人指的是什么?
- php - PHP:使用队列机制处理 csv 文件的最佳选择,以便在 mysql 数据库上进行大量插入
- python - 如何在列表中添加扩展名?
- python - Python requests.raise_for_status() 异常查找输出
- c# - 从子窗体访问主窗体中的控件
- spring - 创建spring项目时出错。: J2EE 组件映射更新
- java - 如何调用 Rest API 并使用该 API 中的数据?
- apache-spark - 使用 Java 在 Spark 中进行映射
- python - 安装 socail-auth-app 后 Django 中的 ModuleNotFoundError
- c++ - 我们可以在 C++ 中使用数组作为priority_queue 元素吗?