Priority Queue
Java의 Queue 인터페이스를 구현한 클래스 중 하나이다.
넣은 순서대로 꺼내는 일반 Queue와 다르게, 항상 우선순위가 높은 요소를 먼저 꺼낸다.
내부적으로 힙(Heap) 자료구조를 사용해서 동작한다.
-
일반 큐는 선형 구조이지만, 우선순위 큐는 논리적으로는
이진 힙(Binary Heap)구조를 기반으로 하며,배열(Array)로 구현된다. 일반적으로는최소 힙(min-heap)으로 구현된다.
(밑의 Min-Heap 작동 구조 예시를 보면 이해가 될 것이다.) -
기본 우선순위는
오름차순이며,내림차순은 생성자에 Comparator를 전달해야함.Collections.reverseOrder() -
삽입 시
heapify up, 삭제 시heapify down연산을 통해 힙 속성을 유지한다. -
내부구조가 이진트리로 되어있기때문에 삽입/삭제의 시간복잡도는
O(log N), peek()의 시간복잡도는O(1)이다.
기본 사용법 (오름차순)
기본은 오름차순이다. 가장 작은 값이 먼저 나온다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(8);
pq.add(1);
System.out.println(pq); // 힙 구조이므로 정렬된 것처럼 보이지는 않음
System.out.println(pq.peek()); // 1 (가장 작은 값)
System.out.println(pq.poll()); // 1 제거 후 반환
System.out.println(pq.peek()); // 2내림차순
Collections.reverseOrder() 사용하여 내림차순 설정.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(5);
pq.add(2);
pq.add(8);
pq.add(1);
System.out.println(pq.peek()); // 8주요메서드
일반 Queue와 동일
https://velog.io/@seha01130/JAVA-큐Queue-메소드-정리
내부구조 (Binary Heap)
실제 정렬된 순서를 유지하는 것이 아닌, 가장 높은 우선순위 값이 루트에 위치하도록 구성된 완전 이진 트리 구조이다.
따라서 System.out.println(pq)를 하면 정렬된 것처럼 보이진 않아도 peek()와 poll()은 항상 정확하게 우선순위대로 동작한다.
🤓 Binary Heap의 특징
완전 이진 트리 형태 (왼쪽부터 차곡차곡 채워짐)
최대/최소 힙에 따라 루트가 가장 큰/작은 값
배열(Array) 로 구현됨 (트리지만 노드 대신 인덱스로 자식/부모를 계산)
| 관계 | 공식 |
|---|---|
| 왼쪽 자식 | 2 * i + 1 |
| 오른쪽 자식 | 2 * i + 2 |
| 부모 | (i - 1) / 2 |
Min-Heap 작동 구조 (PriorityQueue 기본)
1
/ \
3 8
/
5최솟값(1)이 루트
삽입/삭제할 때 트리 구조를 다시 맞춰주는 heapify(정렬) 작업이 필요함
⚙ 삽입 add(), offer()
삽입 순서
- 요소를 배열의 맨 끝에 추가
- 부모 노드와 비교해서 필요하면 교환 (위로 올림, "Heapify Up")
- 부모 인덱스: (i - 1) / 2
- 조건이 맞을 때까지 반복
📍 초기
Heap 배열: [1, 3, 8, 5]
Index: 0 1 2 3
➕ 삽입 0 → [1, 3, 8, 5, 0]
1
/ \
3 8
/ \
5 0 ← 새로 삽입된 위치
👆🏻 Heapify up
0의 인덱스: 4
부모 인덱스: (4 - 1) / 2 = 1 → 값은 3
0은 부모 3보다 작음 → 교환 → [1, 0, 8, 5, 3]
Index: 0 1 2 3 4
값: 1 0 8 5 3
1
/ \
0 8
/ \
5 3
👆🏻 Heapify up
0의 새 인덱스: 1
부모 인덱스: (1 - 1) / 2 = 0 → 값은 1
0은 부모 1보다 작음 → 교환 → [0, 1, 8, 5, 3]
Index: 0 1 2 3 4
값: 0 1 8 5 3
0
/ \
1 8
/ \
5 3삽입된 0이 부모 노드들과 비교해서 위로 올라가고, 힙 조건(부모 ≤ 자식)을 만족할 때까지 계속 교환된다.
⚙ 삭제 동작 poll()
루트(최댓값 or 최솟값)를 제거
마지막 요소를 루트에 위치시킴
자식들과 비교해가며 교환 (아래로 내림, "Heapify Down")
📍 초기
Heap 배열: [1, 3, 8, 5]
Index: 0 1 2 3
1
/ \
3 8
/
5
➖ 루트 요소 제거
poll() → 1 제거 → 5를 루트로 → [5, 3, 8]
5
/ \
3 8
👆🏻 Heapify Down 시작 (루트에서 아래로 내려가며 정렬)
현재 루트 인덱스: 0, 값: 5
자식 인덱스
왼쪽 자식: 2*0 + 1 = 1 → 값 3
오른쪽 자식: 2*0 + 2 = 2 → 값 8
두 자식 중 더 작은 값: 3 (왼쪽 자식)
비교: 5 > 3 → 교환 필요
🔁 교환 수행
5와 3을 교환
배열: [3, 5, 8]
3
/ \
5 8
현재 노드 5의 새 인덱스: 1
자식 인덱스: 2*1 + 1 = 3, 2*1 + 2 = 4 → 배열 끝났음
🚩 정렬 완료!
삭제 결과 배열: [3, 5, 8]