[자료 구조 & 알고리즘]우선순위 큐 : 힙(Heap)

우선순위 큐는 데이터의 우선순위를 관리하는 특수한 자료구조입니다. 일반적인 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In, First Out) 방식으로 작동하지만, "우선순위 큐"는 데이터마다 우선순위를 부여하고, 그 우선순위에 따라 먼저 처리할 데이터를 결정합니다.

우선순위 큐와 힙(Heap)

우선순위 큐는 일반적으로 힙(Heap)자료구조를 기반으로 구현됩니다. 힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드의 값이 자식 노드의 값보다 작거나 큰 특성을 가집니다. 이러한 성질 때문에 우선순위 큐를 효율적으로 구현할 수 있습니다.

• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 항상 작습니다. 이 경우, 우선순위가 가장 높은 데이터가 트리의 루트에 위치합니다.
• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 항상 큽니다. 이 경우, 우선순위가 가장 높은 데이터는 트리의 루트에 위치합니다.

자바에서의 우선순위 큐

자바에서는 우선순위 큐를 사용하기 위해 PriorityQueue 클래스를 제공합니다. 이 클래스는 기본적으로 최소 힙을 사용하여 구현됩니다. 우선순위 큐에 데이터를 넣으면, 값이 작은 데이터부터 먼저 처리됩니다.

 

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 우선순위 큐 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 데이터 추가 (offer)
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(10);

        // 가장 작은 값을 확인 (peek)
        System.out.println("가장 작은 값: " + pq.peek()); // 출력: 1

        // 우선순위가 가장 높은 데이터(가장 작은 값) 제거 (poll)
        System.out.println("제거된 값: " + pq.poll()); // 출력: 1

        // 남아있는 값 확인
        System.out.println("가장 작은 값: " + pq.peek()); // 출력: 3

        // 큐가 비어있는지 확인 (isEmpty)
        System.out.println("큐가 비어있는가? " + pq.isEmpty()); // 출력: false
    }
}

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll());  // 1
System.out.println(pq.poll());  // 3
System.out.println(pq.poll());  // 5