우선순위 큐(Priority Queue)와 힙(Heap)

1. 우선순위 큐란?

일반 큐(Queue)는 FIFO(First-In, First-Out) 구조로 먼저 들어온 데이터가 먼저 나온다.
반면 우선순위 큐(Priority Queue) 는 우선순위가 높은 데이터부터 꺼내는 자료구조이다.

예를 들어, 정수 데이터를 넣었을 때 작은 수가 우선되도록 설정하면, 입력 순서와 상관없이 가장 작은 수부터 꺼낼 수 있다.

2. 자바에서 PriorityQueue 사용

Java에서는 PriorityQueue 클래스를 사용해 쉽게 우선순위 큐를 구현할 수 있다.

Queue<Integer> pq = new PriorityQueue<>();

pq.add(3);
pq.add(1);
pq.add(8);

while (!pq.isEmpty()) {
    System.out.println(pq.remove());
}

결과

1
3
8

→ 기본 PriorityQueue는 min heap(작은 값 우선) 형태

3. 다양한 초기화 방법

1) 컬렉션(Collection)으로부터 생성

List<Integer> list = List.of(1, 4, 2, 3, 5, 6);
Queue<Integer> pq = new PriorityQueue<>(list);

2) 최대 힙(Max Heap)

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

3) 사용자 정의 클래스

우선순위 기준을 직접 정의하려면 Comparable<T>를 구현합니다.

class Person implements Comparable<Person> {
    String name;
    int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public int compareTo(Person o) {
        return this.age - o.age;  // 나이가 적을수록 우선
    }
}

 

Queue<Person> pq = new PriorityQueue<>();
pq.add(new Person("홍길동", 24));
pq.add(new Person("김철수", 21));
pq.add(new Person("김영희", 25));

while (!pq.isEmpty()) {
    Person p = pq.remove();
    System.out.println(p.name + "(" + p.age + ")");
}

결과

김철수(21)
홍길동(24)
김영희(25)

 

4. 힙(Heap)의 시간 복잡도

연산	시간복잡도
힙 생성	O(n)
삽입 (push)	O(log n)
삭제 (pop)	O(log n)

5. 코딩테스트 활용 예시

1. 다익스트라 알고리즘 → 최단 경로 계산에 우선순위 큐 사용
2. 최댓값 / 최솟값 반복 조회 → 데이터를 계속 추가하면서 최댓값·최솟값을 빠르게 찾는 문제