Min-MaxヒープのJava実装ですか？

Question

min-maxヒープで信頼性の高いJava実装を持っている人気のあるライブラリ（Apache、Googleなど）のことを知っていますか？それは最小値と最大値を覗き見ることができるヒープで、O(1)O(log n)の要素ですか？

Answer 1

グアバから：MinMaxPriorityQueue。

Answer 2

java.util.TreeSetクラス。

Answer 3

約com.aliasi.util.MinMaxHeap？これはLingPipeの一部です。残念ながら、licensingが問題になることがあります。

this related paperを参照してください。

ただし、reduceKeyまたはincreaseKeyは実装されていません。

Answer 4

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

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

Answer 5

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; 
} 

Answer 6

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