Min-Max堆的Java实现？

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,谷歌等集合),它有一个最小最大堆的可靠Java实现,这是一个允许在O(1)中查看其最小值和最大值并删除的堆O(log n)中的元素?

6 个解决方案

#1

From Guava: MinMaxPriorityQueue.

来自Guava:MinMaxPriorityQueue。

#2

Instead of a max-min heap, could you use two instances of a java.util.PriorityQueue containing 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的两个实例而不是max-min堆吗?第一个实例将通过一个比较器,它将最大值放在头部,第二个实例将使用一个比较器,它将最小值放在头部。

The downside is that add, delete, etc would have to be performed on both structures, but it should satisfy your requirements.

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

#3

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

}

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:

欲了解更多信息,请访问:

#4

How about com.aliasi.util.MinMaxHeap? This is part of LingPipe; unfortunately, the licensing may be a problem.

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

See this related paper.

见这篇相关论文。

Doesn't implement decreaseKey or increaseKey, though.

但是,不实现reduceKey或increaseKey。

#5

The java.util.TreeSet class.

java.util.TreeSet类。

#6

-8

private void heapifyUp(int current) {
int parent = (current - 1) / 2;
if (current < 0)return;
while (current > 0 && arr[current] > arr[parent]) {
   int temp = arr[parent];
   arr[parent] = arr[current];
   arr[current] = temp;
   current = parent;
  parent = (current - 1) / 2;
 } return;
}

#1