您是否知道一个受欢迎的库（如Apache、Google和collections）具有可靠的Java实现的min-max堆，即堆可以在O(1)时间内查看其最小值和最大值，并且可以在O(log n)时间内删除元素？
Java实现最小-最大堆？
48
- Yuval Adam
7个回答
39
Java有很好的工具来实现最小堆和最大堆。我的建议是使用优先队列数据结构来实现这些堆。要使用优先队列实现最大堆，请尝试以下操作：
import java.util.PriorityQueue;
public class MaxHeapWithPriorityQueue {
public static void main(String args[]) {
// create priority queue
PriorityQueue<Integer> prq = new PriorityQueue<>(Collections.reverseOrder());
// insert values in the queue
prq.add(6);
prq.add(9);
prq.add(5);
prq.add(64);
prq.add(6);
//print values
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
}
要使用优先队列实现最小堆，请尝试以下方法：
import java.util.PriorityQueue;
public class MinHeapWithPriorityQueue {
public static void main(String args[]) {
// create priority queue
PriorityQueue< Integer > prq = new PriorityQueue <> ();
// insert values in the queue
prq.add(6);
prq.add(9);
prq.add(5);
prq.add(64);
prq.add(6);
//print values
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
}
更多信息请访问：
- Mohammad
16
“更方便”是什么意思？您能详细解释一下吗？ - Mohammad
Collections.reverseOrder() 还返回一个比较器。因此，它可以在 PriorityQueue 构造函数 中使用。两种方法都可以工作。但对我来说，reverseOrder 更加明显。就这些。 - Michael Berdyshev
2对于这一部分，我使用了lambda表达式（Java 8）。然而，这基于个人偏好。你的建议也很好。我感谢你提供的替代方案。 - Mohammad
4在Lambda表达式中，由于整数溢出的问题，通过减法进行比较的技巧很容易被破坏。建议使用简单的比较方法：
(x, y) -> x < y ? -1 : x == y ? 0 : 1。 - Ruifeng Ma显示剩余11条评论
28
不一定非要使用最大-最小堆，您是否可以使用两个实例的java.util.PriorityQueue来包含相同的元素？第一个实例将传递一个比较器，该比较器将把最大值放在头部，而第二个实例将使用将最小值放在头部的比较器。
缺点是添加、删除等操作必须在两个结构上执行，但它应该能够满足您的要求。
- Il-Bhima
4
6根据要求，使得在O(1)的时间内查找根节点并在O(log.n)的时间复杂度内删除根节点，这个回答很好。但是需要注意的是，优先队列并没有实现所有的堆操作（例如，decreaseKey和increaseKey）。 - dty
7请注意，没有参数的
remove() 方法会从队列头部删除元素，其时间复杂度为 O(log(n))，而有参数的 remove(Object o) 方法时间复杂度为 O(n)。参考链接：http://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html - erwaman4因为删除操作不再是O(log n)，所以被踩了。从其中一个队列中删除最小值的时间复杂度是O(log n)，但是删除相同项，它将在另一个队列的末尾，时间复杂度是O(n)。 - Jim Mischel
1@JimMischel 这正是我的想法，但后来我意识到我们仍然可以按以下方式使两个堆的解决方案可行。当我们提取/查看最大值时，只从最大堆中进行, 最小堆也同理。这当然会导致两个不一致的堆。我们跟踪最后一个被提取的最大值和最后一个被提取的最小值，以便在它们重合时，数据结构为空。如果我们不需要支持插入和键值更改（在提取操作完成后）, 那么这将起作用，而 OP 没有指定为要求。 - flow2k
9
最小堆： PriorityQueue minHeap = new PriorityQueue<>();
最大堆： PriorityQueue maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
- Vip
8
你可以简单地传递要用于比较元素的比较器。即使你想根据某些属性对对象进行排序，这也会变得很有用。看下面的示例：
Min Heap :
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b);
Max Heap :
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
Min Heap for Objects
PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj1.getId() - obj2.getId());
Max Heap for Objects
PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj2.getId() - obj1.getId());
- Fahad Israr
3
怎么看 com.aliasi.util.MinMaxHeap？这是 LingPipe 的一部分；不过，licensing 可能会成为一个问题。
看看 this related paper。
不过没有实现 decreaseKey 或 increaseKey。
看看 this related paper。
不过没有实现 decreaseKey 或 increaseKey。
- NamshubWriter
0
- Nat
6
2我需要支持重复值...在这方面，集合有点棘手。 - Yuval Adam
3TreeSet实现大多数操作的时间复杂度为O(log n)，但要求在O(1)的时间内查看最小值和最大值。 - Avi
TreeSet也没有decreaseKey或increaseKey操作，这是堆的一个明确操作之一。请参见http://en.wikipedia.org/wiki/Heap_(data_structure)。 - NamshubWriter
1如果您需要支持重复值，可以使用Apache Commons Collections中的TreeBag（http://commons.apache.org/collections/api-release/org/apache/commons/collections/bag/TreeBag.html）或Google Collections中的TreeMultiset（http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/TreeMultiset.html）。如果您需要增加或减少键值，则可以简单地删除元素并重新添加。 - newacct
2或者使用一个将键映射到计数的TreeMap。TreeSet实际上是在底层使用TreeMap实现的。 - Nat
@YuvalAdam 可以通过将键替换为
[key，stamp]对来实现重复值和稳定排序，因此首先对键进行比较，然后对戳记进行比较。但是，TreeSet不能替代最大-最小堆双端队列。 - Alex Salauyou网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
Deque实现。 - Alex SalauyouDeque#removeFirstOccurrence()和removeLastOccurence()，因为最小-最大堆的不稳定性。 - Alex SalauyouDeque的文档规定，当它像队列一样使用时，会产生FIFO行为。MinMaxPriorityQueue理论上可以实现这些方法，但无法满足契约。 - Louis WassermanMinMaxPriorityQueue源代码后，我意识到它并没有实现一个“真正的” _min-max堆_（很少有人知道），而是仅仅使用了两个堆，一个最小堆和一个最大堆，将它们组合在一起来实现一个双端优先队列。 - nbro