Min-Max堆的Java实现？

Question

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

Answer 1

来自番石榴:MinMaxPriorityQueue.

Answer 2

您可以使用包含相同元素的java.util.PriorityQueue的两个实例而不是max-min堆吗？第一个实例将通过一个比较器,它将最大值放在头部,第二个实例将使用一个比较器,它将最小值放在头部.

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

Answer 3

Java有很好的工具来实现最小和最大堆.我的建议是使用优先级队列数据结构来实现这些堆.要实现具有优先级队列的最大堆,请尝试:

import java.util.PriorityQueue;

public class MaxHeapWithPriorityQueue {

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

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

最大堆 ​​PriorityQueue maxHeap= new PriorityQueue<>(Comparator.reverseOrder());

Answer 5

那么您可以简单地传递用于比较元素的比较器。即使您想根据某些属性对对象进行排序，这也会变得很有用。看下面的例子：

• 最小堆：

  PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b);
  

• 最大堆：

  PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
  

• 对象的最小堆

  PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj1.getId() - obj2.getId());
  

• 对象的最大堆

  PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj2.getId() - obj1.getId());