자바에서 Heap 사용하는 방법

Java에서  Heap 사용하기

Java에서는 Collection으로 Heap이 없다. 하지만 Max-Heap과 Min-Heap을  Primary Queue를 활용하여 구현할 수 있다.

이번 시간에는 Primary Queue를 활용해 Heap을 구현하는 방법을 알아보고자 한다.

 

Heap이라는 자료구조는 값들이 모여있는 자료구조를 트리로 구현하였다고 할 때, 루트에 위치하는 값이 최대 혹은 최소값이 되는 자료구조를 의미한다.

최소 힙 사용하기

최소힙을 사용하는 것은 Primary Queue를 그대로 사용해주면 된다.

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

이렇게 사용하여 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최소값이 된다.

 

Primary Queue는 우선순위 큐로 우선순위가 가장 낮은 값이 먼저 나오게 되어 있습니다. 우선순위가 낮다는 것은 Integer를 넣었을 때, 최소값으로 판단되므로 이렇게 구현할 수 있다.

최대 힙 사용하기

최대 힙을 사용하는 방법은 Comparator 값을 세팅해주어 사용할 수 있다.

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

Integer의 compare의 값이 default로 들어가게 되는데 이 값을 -로 바꾸어 주면 Max Heap이 된다.

 

 

잘못된 정보나 궁금한점은 편하게 댓글 달아주시면 감사하겠습니다 :)