우선순위 큐(Priority Queue)란?

우선순위 큐는 큐(Queue)의 한 종류로, 원소들이 우선순위에 따라 정렬되어 있는 자료 구조입니다. 일반적인 큐와는 달리, 우선순위 큐는 데이터를 꺼낼 때 우선순위가 가장 높은 데이터부터 꺼내게 됩니다.

언제 사용하는가?

작은 값이나 큰 값을 빠르게 찾아야 할 때
데이터를 정렬된 상태로 유지하면서 삽입과 삭제가 자주 발생하는 경우
다익스트라(Dijkstra) 알고리즘, 힙 정렬(Heap Sort) 등 알고리즘에 자주 사용됩니다.

자료 구조와 시간 복잡도

자료 구조: 일반적으로 힙(Heap)을 사용합니다.
시간 복잡도: 삽입과 삭제 모두 O(log N)입니다.

주요 메소드

add(E e): 원소 추가
poll(): 가장 우선순위가 높은 원소 삭제 및 반환
peek(): 가장 우선순위가 높은 원소 조회
remove(Object o): 특정 원소 삭제
clear(): 모든 원소 삭제

제네릭과 자료형

Java에서 PriorityQueue는 제네릭을 지원합니다. 따라서 어떠한 타입의 객체도 저장할 수 있습니다. 하지만 이 객체는 Comparable 인터페이스를 구현해야 하거나 별도의 Comparator를 제공해야 합니다.

// 예시 코드
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // Integer 타입을 가진 우선순위 큐 생성
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 원소 추가
        pq.add(10);
        pq.add(30);
        pq.add(20);

        // 원소 꺼내기
        System.out.println(pq.poll()); // 출력: 10
        System.out.println(pq.poll()); // 출력: 20
    }
}

예제: K개 정렬된 배열 병합하기

K개의 정렬된 배열이 주어졌을 때, 이를 하나의 정렬된 배열로 병합하려고 합니다. 예를 들어,

배열 1: [1, 4, 7]
배열 2: [2, 5, 8]
배열 3: [3, 6, 9]

이렇게 3개의 정렬된 배열을 하나로 병합하면 [1, 2, 3, 4, 5, 6, 7, 8, 9]가 됩니다.

이 문제를 효율적으로 해결하기 위해서 우선순위 큐를 사용할 수 있습니다.

import java.util.PriorityQueue;

class ArrayElement implements Comparable<ArrayElement> {
    public int array, index, value;

    public ArrayElement(int array, int index, int value) {
        this.array = array;
        this.index = index;
        this.value = value;
    }

    public int compareTo(ArrayElement o) {
        return Integer.compare(this.value, o.value);
    }
}

public class Main {
    public static void main(String[] args) {
        // 주어진 K개의 배열
        int[][] arrays = {
            {1, 4, 7},
            {2, 5, 8},
            {3, 6, 9}
        };

        PriorityQueue<ArrayElement> pq = new PriorityQueue<>();

        // 각 배열의 첫 번째 원소를 큐에 삽입
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                pq.add(new ArrayElement(i, 0, arrays[i][0]));
            }
        }

        // 결과를 저장할 배열
        int[] result = new int[arrays.length * 3];
        int resultIndex = 0;

        while (!pq.isEmpty()) {
            ArrayElement elem = pq.poll();
            result[resultIndex++] = elem.value;

            if (elem.index + 1 < arrays[elem.array].length) {
                pq.add(new ArrayElement(elem.array, elem.index + 1, arrays[elem.array][elem.index + 1]));
            }
        }

        // 결과 출력
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }
}

이 코드는 우선순위 큐를 사용하여 K개의 정렬된 배열을 하나로 병합하는 문제를 해결합니다. 각 배열의 첫 번째 원소를 우선순위 큐에 삽입한 후, 가장 작은 원소를 꺼내 결과 배열에 저장합니다. 그리고 해당 원소의 다음 원소를 다시 우선순위 큐에 삽입합니다. 이 과정을 반복하여 최종적으로 하나의 정렬된 배열을 얻을 수 있습니다.

우선순위 큐의 내부 동작

우선순위 큐에대해 전체적인 이해가 되었다면 보다 자세히 알아봅시다.

우선순위 큐는 일반적으로 힙(Heap) 이라는 자료구조를 사용하여 구현됩니다. 힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 힙의 각 노드는 자식 노드보다 작거나 큰 값을 가집니다. 이런 특성을 이용하여 우선순위 큐를 효율적으로 구현할 수 있습니다.

삽입 연산 (`add()` or `offer()`)

끝 노드 추가: 새로운 원소는 일단 힙의 마지막 노드로 추가됩니다.
힙 성질 유지: 마지막 노드부터 루트 노드까지 비교하며 자신의 부모 노드와 위치를 교환합니다. (최소 힙의 경우 부모가 더 크다면, 최대 힙의 경우 부모가 더 작다면)

삭제 연산 (`poll()`)

루트 노드 반환: 힙의 루트 노드(최소 or 최대)를 반환합니다.
마지막 노드 이동: 힙의 마지막 노드를 루트 노드로 이동시킵니다.
힙 성질 유지: 루트 노드부터 리프 노드까지 내려가며 자신의 자식 노드와 비교하여 힙 성질을 유지하도록 위치를 교환합니다.

조회 연산 (`peek()`)

루트 노드 반환: 힙의 루트 노드를 반환합니다. 이 연산은 O(1)의 시간 복잡도를 가집니다.

시간 복잡도

add(): O(log N)
poll(): O(log N)
peek(): O(1)

예시: 최소 힙

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(3);  // 3
minHeap.add(1);  // 1 3
minHeap.add(4);  // 1 3 4
minHeap.add(1);  // 1 1 4 3
minHeap.add(5);  // 1 1 4 3 5
int min = minHeap.poll();  // min = 1, heap = 1 3 4 5

이렇게 우선순위 큐는 힙을 기반으로 동작하여 삽입, 삭제, 조회 연산을 빠르게 수행할 수 있습니다. 특히 복잡한 알고리즘 문제나 데이터 처리 작업에서 이러한 특성이 큰 장점으로 작용합니다.

최소 힙과 최대 힙

최소 힙 (Min-Heap)

힙의 루트 노드에는 힙 내에서 최소값이 저장됩니다.
부모 노드의 값은 자식 노드의 값보다 항상 작거나 같습니다.

최대 힙 (Max-Heap)

힙의 루트 노드에는 힙 내에서 최대값이 저장됩니다.
부모 노드의 값은 자식 노드의 값보다 항상 크거나 같습니다.

특징

힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가져야 합니다.
일반적으로 배열을 이용해 힙을 구현합니다. 배열의 인덱스를 이용하여 부모 노드와 자식 노드의 관계를 쉽게 나타낼 수 있습니다.

배열에서의 인덱스 관계

부모 노드의 인덱스: p
왼쪽 자식 노드의 인덱스: 2 * p
오른쪽 자식 노드의 인덱스: 2 * p + 1

Java로 힙 구현하기

최소 힙

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 원소 추가
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(4);
        minHeap.add(1);
        minHeap.add(5);

        // 최소 원소 조회
        System.out.println(minHeap.peek());  // Output: 1

        // 최소 원소 삭제 및 반환
        System.out.println(minHeap.poll());  // Output: 1
    }
}

최대 힙

Java의 PriorityQueue는 기본적으로 최소 힙입니다. 최대 힙을 구현하려면, 커스텀 비교자를 제공해야 합니다.

import java.util.PriorityQueue;
import java.util.Comparator;

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        // 원소 추가
        maxHeap.add(3);
        maxHeap.add(1);
        maxHeap.add(4);
        maxHeap.add(1);
        maxHeap.add(5);

        // 최대 원소 조회
        System.out.println(maxHeap.peek());  // Output: 5

        // 최대 원소 삭제 및 반환
        System.out.println(maxHeap.poll());  // Output: 5
    }
}

이렇게 Java에서는 PriorityQueue 클래스를 이용하여 쉽게 최소 힙과 최대 힙을 구현할 수 있습니다. 힙에 원소를 추가하거나 삭제하는 연산은 대부분 O(log N)의 시간 복잡도를 가집니다.

저작자표시 비영리 변경금지