[JAVA] 우선순위 큐 (PriorityQueue)

우선순위 큐 (PriorityQueue)

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

우선순위 큐를 구현하는 방법은 다양하다.

 

① 단순히 리스트를 이용하여 구현

② 힙(Heap)을 이용하여 구현

 

데이터의 개수가 N개일 때, 구현 방식에 따라 시간 복잡도가 다르다.

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이 경우 시간 복잡도는 O(NlogN) 이다.

 

힙(Heap)의 특징

• 힙(Heap)은 완전이진트리의 일종
• 힙(Heap)에서는 항상 루트노드를 제거한다.

 

최소 힙(min heap)

• 루트노드가 가장 작은 값을 가진다. 따라서 값이 작은 데이터가 우선적으로 제거된다.

 

최대 힙(max heap)

• 루트노드가 가장 큰 값을 가진다. 따라서 값이 큰 데이터가 우선적으로 제거된다.

 

완전이진트리 (Complete Binary Tree)

완전이진트리란 루트노드부터 시작하여 왼쪽 자식노드, 오른쪽 자식노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미한다.

최소 힙 구성 함수 Min-Heapify()

상향식 : 부모노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.

 

힙에 새로운 원소가 삽입되었을 때, O(logN)의 시간복잡도로 힙 성질을 할 수 있다.

 

원소가 제거되었을 때 O(logN)의 시간복잡도로 힙 성질을 유지할 수 있다. 원소를 제거할 때는 가장 마지막 노드가 루트노드의 위치에 오도록 한다.

 

이후에 루트노드에서부터 하향식으로 Heapify()를 진행한다.

---

우선순위 큐 구현

기본은 우선순위가 낮은 숫자가 부여되고 만약 높은 숫자가 우선순위가 되게 하고 싶다면 선언 시, Collections.reverseOrder()메서드를 활용한다.

public class Main {
    public static void main(String[] args) {

        // 우선순위가 낮은 숫자 순 
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // 우선순위가 높은 숫자 순
        PriorityQueue<Integer> queue2 = new PriorityQueue<>(Collections.reverseOrder());

        queue.add(2);
        queue.add(1);
        queue.offer(3);

        System.out.println(queue.poll()); // 1  출력

    }
}