Java에 힙이 있나요?

Java에 힙이 있나요?

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

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

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

최소 힙: --> 최소 요소를 항상 맨 위에 유지하여 O(1)에서 액세스할 수 있도록 합니다.

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

Max Heap : --> 최대 요소를 항상 상기와 같은 순서로 맨 위에 둡니다.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

어느쪽과 같습니까?(Integer o1, Integer o2) -> Integer.compare(o2, o1)또는- Integer.compare(o1, o2)다른 답변에서 제시된 바와 같이

다음 중 하나를 사용할 수 있습니다.
add--> 요소를 큐에 추가합니다.O(log n)
remove--> 최소값/최대값을 가져와 삭제합니다.O(log n)
peek-->최소/최대값을 취득하지만 삭제하지 않는다.O (1)

최소 힙:

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

Java priority의 경우큐는 힙으로 사용할 수 있습니다.

최소 힙

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

최대 힙

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

우선 순위.큐는 히프를 사용합니다.https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html의 Oracle 매뉴얼에 따르면 이는 바이너리 힙의 구현인 것으로 보입니다.fibonacci 또는 pairing heap의 정식 실장은 없다고 생각합니다만, 둘 중 어느 쪽이라도 사용할 수 있으면 좋겠다고 생각하고 있습니다.

아니요, 없습니다만 Priority Queue를 힙으로 사용할 수 있습니다.Oracle에 의해 공식적으로 Priority Queue를 힙으로 사용하도록 지시받았습니다. 자세한 내용은 이 링크를 참조하십시오.

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

PriorityQueue<Integer> MaxHeap = new PriorityQueue<>(Comparator.reverseOrder());

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

Java 문서에서PriorityQueue1.5가 사용할 클래스이기 때문에 사용할 수 있습니다.

이 코드는Min Heap priority를 만듭니다.기본 초기 용량(11)으로 큐잉하여 min이 맨 위에 있는 자연 순서에 따라 요소를 정렬합니다.

//MIN HEAP
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//equivalent to 
PriorityQueue<Integer> minHeap = new PriorityQueue<>(11);

특수 순서를 구현하려면 이 생성자로 비교 연산자를 재정의해야 합니다.

PriorityQueue​(int initialCapacity, Comparator<? super E> comparator);

1.8부터 이 버전도 있습니다.

PriorityQueue​(Comparator<? super E> comparator);

이 기능을 사용하면,Max Heap등 보다 우아한 방법으로

//MAX HEAP
PriorityQueue<Integer> maxHeap = 
new PriorityQueue<>((n1,n2) -> Integer.compare(n2,n1));
//equivalent to 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

특별한 경우 가상의 레스토랑까지의 거리에 따라 고객을 주문하는 시나리오에서 사용자 지정 객체의 자연스러운 순서를 보여주는 이 예를 확인하십시오.

import java.util.List;
import java.util.PriorityQueue;

public class DeliveryHandler {

    private static final Address restaurant = new Address(5.0, 5.0);

    private static class Address implements Comparable<Address> {
        public double x, y;

        public Address(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double distanceToShop() {
            return Math.pow(restaurant.x - x, 2) + Math.pow(restaurant.y - y, 2);
        }

        @Override
        public int compareTo(Address other) {
            return Double.compare(this.distanceToShop(), other.distanceToShop());
        }

        @Override
        public String toString() {
            return "Address {x=%s, y=%s}".formatted(x, y);
        }
    }

    public static void main(String[] args) {
        List<Address> customers = List.of(
                new Address(13, 14),
                new Address(3, 1),
                new Address(9, 20),
                new Address(12, 4),
                new Address(4, 4));

        PriorityQueue<Address> queueServingClosest = new PriorityQueue<>();
        queueServingClosest.addAll(customers);
        while (!queueServingClosest.isEmpty()) {
            System.out.println(queueServingClosest.remove());
        }

        /* Prints
        Address {x=4.0, y=4.0}
        Address {x=3.0, y=1.0}
        Address {x=12.0, y=4.0}
        Address {x=13.0, y=14.0}
        Address {x=9.0, y=20.0}
         */

        PriorityQueue<Address> queueServingFurthest = new PriorityQueue<>(
                (a1, a2) -> Double.compare(a2.distanceToShop(), a1.distanceToShop())
        );
        queueServingFurthest.addAll(customers);
        while (!queueServingFurthest.isEmpty()) {
            System.out.println(queueServingFurthest.remove());
        }

        /* Prints
        Address {x=9.0, y=20.0}
        Address {x=13.0, y=14.0}
        Address {x=12.0, y=4.0}
        Address {x=3.0, y=1.0}
        Address {x=4.0, y=4.0}
         */
    }
}

참조

1- https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

2- https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

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