자바에 힙이 있습니까?

자바에 힙이 있습니까?

---

C ++ 라이브러리를 Java로 포팅 중이며 힙 데이터 구조가 필요합니다. 표준 구현이 있습니까? 아니면 직접해야합니까?

---

최소 힙 :

        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

최대 힙 :

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return - Integer.compare(o1,o2);
        }
    });

---

PriorityQueue는 힙을 사용합니다. https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html 의 oracle 문서에 따르면 바이너리 힙의 구현 인 것 같습니다. 피보나치 또는 페어링 힙의 공식 구현이 없다고 생각하지만 두 가지 중 하나를 사용할 수 있으면 좋겠습니다.

---

Java 8의 경우 기존 답변 업데이트 :

Java Priority Queue를 힙으로 사용할 수 있습니다.

Min Heap : -> min 요소를 항상 맨 위에 유지하므로 O (1)에서 액세스 할 수 있습니다.

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

Max Heap : -> 위와 같은 순서로 max 요소를 항상 맨 위에 유지합니다.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((Integer o1, Integer o2) -> (- Integer.compare(o1,o2)));

그리고 다음을 사용할 수 있습니다
add.-> 큐에 요소를 추가합니다. O (log n)
remove-> 최소 / 최대를 구하고 제거합니다. O (log n)
peek-> 가져 오지만 최소 / 최대는 제거하지 않습니다. O (1)

---

기본 작업 (추가, 제거, 포함)에 대한 log (n) 시간을 보장하는 TreeSet 을 고려할 수도 있습니다.

참조 URL : https://stackoverflow.com/questions/14165325/is-there-a-heap-in-java