최소 - 최대 힙에 대한 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의 두 인스턴스를 사용할 수 있습니까? 첫 번째 인스턴스는 머리에 최대 값을 넣는 비교기를 전달하고 두 번째 인스턴스는 머리에 최소값을 가져 오는 비교기를 사용합니다.

두 가지 구조에서 추가, 삭제 등을 수행해야하지만 사용자의 요구 사항을 충족시켜야한다는 단점이 있습니다.

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