java - 最小-最大ヒープのJava実装？

Question

O(1)最小値と最大値をのぞき見し、の要素を削除できるヒープである、最小-最大ヒープの信頼性の高いJava実装を備えた人気のあるライブラリ（Apache、Googleなどのコレクション）を知っていますO(log n)か？

Answer 1

グアバから：MinMaxPriorityQueue。

Answer 2

max-minヒープの代わりに、同じ要素を含むjava.util.PriorityQueueの2つのインスタンスを使用できますか？最初のインスタンスには、最大値を先頭に置くコンパレータが渡され、2番目のインスタンスには、最小値を先頭に置くコンパレータが渡されます。

欠点は、追加、削除などを両方の構造で実行する必要があることですが、要件を満たす必要があります。

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 <>（）;

最大ヒープ PriorityQueuemaxHeap= new PriorityQueue <>（Comparator.reverseOrder（））;

Answer 5

com.aliasi.util.MinMaxHeapはどうですか？これはLingPipeの一部です; 残念ながら、ライセンスが問題になる可能性があります。

この関連論文を参照してください。

ただし、decreaseKeyまたはincreaseKeyは実装していません。

Answer 6

java.util.TreeSetクラス。