最小最大堆的 Java 实现？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1098277/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java implementation for Min-Max Heap?
提问by Yuval Adam
Do you know of a popular library (Apache, Google, etc, collections) which has a reliable Java implementation for a min-max heap, that is a heap which allows to peek its minimum and maximum value in O(1)and to remove an element in O(log n)?
您是否知道一个流行的库（Apache、Google 等，集合），它具有可靠的最小-最大堆的 Java 实现，该堆允许查看其最小值和最大值O(1)并删除其中的元素O(log n)？
采纳答案by Louis Wasserman
From Guava: MinMaxPriorityQueue.
来自番石榴：MinMaxPriorityQueue。
回答by Nat
The java.util.TreeSetclass.
回答by NamshubWriter
How about com.aliasi.util.MinMaxHeap? This is part of LingPipe; unfortunately, the licensingmay be a problem.
com.aliasi.util.MinMaxHeap怎么样？这是LingPipe 的一部分；不幸的是，许可可能是一个问题。
See this related paper.
请参阅此相关文件。
Doesn't implement decreaseKey or increaseKey, though.
但是，不实现decreaseKey 或increaseKey。
回答by Il-Bhima
Instead of a max-min heap, could you use two instances of a java.util.PriorityQueuecontaining the same elements? The first instance would be passed a comparator which puts the maximum at the head, and the second instance would use a comparator which puts the minimum at the head.
您可以使用包含相同元素的java.util.PriorityQueue 的两个实例来代替最大-最小堆吗？第一个实例将传递一个比较器，该比较器将最大值放在头部，第二个实例将使用一个比较器，将最小值放在头部。
The downside is that add, delete, etc would have to be performed on both structures, but it should satisfy your requirements.
缺点是必须在两个结构上执行添加、删除等操作，但它应该满足您的要求。
回答by Mohammad
Java has good tools in order to implement min and max heaps. My suggestion is using the priority queue data structure in order to implement these heaps. For implementing the max heap with priority queue try this:
Java 有很好的工具来实现最小和最大堆。我的建议是使用优先队列数据结构来实现这些堆。要使用优先级队列实现最大堆，请尝试以下操作：
import java.util.PriorityQueue;
public class MaxHeapWithPriorityQueue {
public static void main(String args[]) {
// create priority queue
PriorityQueue<Integer> prq = new PriorityQueue<>(Comparator.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()+" ");
}
}
}
For implementing the min heap with priority queue, try this:
要使用优先级队列实现最小堆，请尝试以下操作：
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()+" ");
}
}
}
For more information, please visit:
欲了解更多信息，请访问：
