[Java] Heap(힙)과 Priority Queue(우선순위 큐)

힙과 우선순위 큐

결론부터 말하자면, 우선순위 큐는 ADT(Abstract Data Type) 이고, 힙은 우선순위 큐의 개념을 구현한 것이다.

ADT
구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 기능이 있는지를 설명하고 나열한 것.
즉, 구현은 하지 않고 어떠한 기능과 어떠한 작동원리를 가지는지 추상적으로 설명한 것이다.

우선순위 큐는 단순 FIFO구조가 아니라, 각 큐에 들어오는 원소마다 우선순위가 정해져 있다.

 

1. 만약, 우선순위가 높은 순서대로 큐에서 제거하기로 했다면 큐에 들어온 순서대로 원소가 제거되는 것이 아니라 우선순위가 높은 순서대로 큐에서 제거된다.
2. 만약, 우선순위가 낮은 순서대로 큐에서 제거하기로 했다면 큐에 들어온 순서대로 원소가 제거되는 것이 아니라 우선순위가 낮은 순서대로 큐에서 제거된다.

 

우선순위 큐는 단순히 ADT이고, 이를 구현한 것이 힙이라고 위에서 말했다.

따라서 1의 경우를 구현한 것을 Max Heap(최대 힙), 2의 경우를 구현한 것을 Min Heap(최소 힙)이라고 한다.

• 우선순위 큐는 완전 이진트리를 이용하여 힙으로 구현한다.
• 시간 복잡도는 삽입과 삭제 모두 O(log N)이다.

자세한 내용은 아래의 동영상을 보고 학습하는 것을 추천한다.

https://youtu.be/P-FTb1faxlo?si=Pak-seuRg2veRZFz

 

자바에서 우선순위 큐 사용하기

PriorityQueue 클래스

• PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 한다.
• Comparable 또는 Comparator 인터페이스를 구현하면 compareTo() 또는 Compare() 메소드를 오버라이딩 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출해준다.

 

최소 힙

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

• 처리될 원소가 integer 타입인 최소 힙 선언
• java.util.PriorityQueue를 import해줘야 한다.

 

최대 힙

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

또는

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

• 처리될 원소가 integer 타입인 최대 힙 선언
• java.util.PriorityQueue를 import해줘야 한다.
• 첫 번째 방법은 Collections클래스의 정적 메소드인 reverseOrder()를 이용해서 최소힙과 반대로 정렬을 하여 최대힙을 만든다.
• 두 번째 방법은 Comparator인터페이스의 구현 객체를 익명으로 만들고, compare메소드를 오버라이딩하여 최소힙과 반대로 정렬을 하여 최대힙을 만든다.

 

메소드

추가

heap.add(1); // 1을 삽입
heap.offer(1); // 1을 삽입

add()메소드와 offer() 메소드의 차이점은 문제 상황에서 예외를 발생시키는가 아니면 false를 리턴하느냐에 있다.

add()는 삽입에 실패할 경우 예외를 발생시키지만, offer는 false를 리턴한다.

 

삭제

heap.poll(); //우선순위가 가장 높은 원소를 삭제
heap.remove(); //우선순위가 가장 높은 원소를 삭제
heap.clear(); //힙을 초기화

remove()메소드와 poll() 메소드의 차이점은 문제 상황에서 예외를 발생시키는가 아니면 null을 리턴하느냐에 있다.

remove()는 삭제에 실패할 경우(또는 큐가 비어있을 경우) 예외를 발생시키지만, poll()는 null을 리턴한다.

 

우선순위가 가장 높은 값 확인

heap.peek(); //우선순위가 가장 높은값 리턴
heap.element(); //우선순위가 가장 높은값 리턴

element()는 큐가 비어있을 경우 예외를 발생시키지만, peek()는 null을 리턴한다.