java - 最小最大堆的Java实现？

Question

你知道一个流行的库（Apache、Google 等，集合），它有一个可靠的 Java 实现最小-最大堆，这是一个允许查看其最小值和最大值O(1)并删除元素的堆O(log n)？

Answer 1

来自番石榴：MinMaxPriorityQueue。

Answer 2

您可以使用包含相同元素的java.util.PriorityQueue的两个实例来代替最大最小堆吗？第一个实例将通过一个比较器，将最大值放在首位，第二个实例将使用一个比较器，将最小值放在首位。

缺点是必须在两个结构上执行添加、删除等操作，但它应该满足您的要求。

Answer 3

Java 有很好的工具来实现最小和最大堆。我的建议是使用优先队列数据结构来实现这些堆。要使用优先级队列实现最大堆，请尝试以下操作：

import java.util.PriorityQueue;

public class MaxHeapWithPriorityQueue {

    public static void main(String args[]) {
    // create priority queue
    PriorityQueue<Integer> prq = new PriorityQueue<>((a,b)->b-a);

    // 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()+" ");
        }
    }

}

欲了解更多信息，请访问：

• https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MaxHeapWithPriorityQueue.java

• https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MinHeapWithPriorityQueue.java

Answer 4

最小堆： PriorityQueue minHeap= new PriorityQueue<>();

Max Heap PriorityQueue maxHeap= new PriorityQueue<>(Comparator.reverseOrder());

Answer 5

com.aliasi.util.MinMaxHeap怎么样？这是LingPipe的一部分；不幸的是，许可可能是个问题。

请参阅此相关论文。

但是，没有实现 reduceKey 或 increaseKey。

Answer 6

java.util.TreeSet类。