[Java] PriorityQueue (우선순위 큐)
목차
Queue?
PriorityQueue (우선순위 큐)
PriorityQueue 사용법
- 선언
- 추가
- 삭제
- 출력
- 기타
우선순위 큐 (PriorityQueue) 정리
# Queue?
- 큐(Queue)는 FIFO(First In First Out)인 자료구조.
- 먼저들어온게 먼저 나간다.
# PriorityQueue (우선순위 큐)
- 우선순위를 정해서 그 우선 순위가 높은게 먼저 나가는 자료구조
- 보통 Heap 자료구조를 이용해 구현.
- 입력받은 데이터를 이용하여 최대힙 또는 최소힙을 구성해서 루트 노드의 데이터를 꺼낸다.
- null을 허용하지 않는다
- 비교할 수 없는 객체는 만들 수 없다
- 내부구조 : 이진트리 힙
- 삽입, 삭제시 시간복잡도 : O(logn)
PriorityQueue 사용법
# 선언
import java.util.Collections;
import java.util.PriorityQueue;
PriorityQueue<Integer> q1 = new PriorityQueue<>(); // 1
PriorityQueue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder()); // 2
PriorityQueue<String> q3 = new PriorityQueue<>(); // 31. 낮은 순자순
2. 높은 숫자순 (Collections.reverseOrder() : 역순)
3. 낮은 문자순
# 추가
q1.add(3);
q1.offer(10);add(e) : 삽입에 성공하면 true를 반환, 여유 공간이 없어서 삽입에 실패하면 IllegalStateException을 발생
offer(e) : 성공하면 true 실패하면 false 반환
추가 과정
1. 우선순위 큐에 숫자 6 추가
2. 10(부모)이랑 비교해서 작은 값이기 때문에 스왑
3. 1(부모)이랑 비교해서 큰 값이기 때문에 스왑X
# 삭제
q1.poll();
q1.remove();
q1.clear();poll() : 우선순위가 가장 높은 값 제거, 큐가 비어있을때는 null을 리턴
remove() : 우선순위가 가장 높은 값 제거, 비어있으면 예외발생
remove(Object o) : o 제거
clear() : 우선순위 큐의 모든 값 삭제
삭제 과정
1. 루트 노드(1)랑 마지막 노드(13)랑 스왑
2. 마지막 노드가 된 1 제거
3. 부모 노드(6)랑 자식 노드(15, 13)를 비교하여 더 작은 값이랑 스왑
4. 부모 노드(13)이랑 자식 노드(17)를 비교하지만 부모 노드가 더 큰 값이기 때문에 스왑X
# 값 출력 (제거X)
q1.peek();
q1.element();peek() : 우선순위가 가장 높은 값 출력, 비어있으면 null
element() : 우선순위가 가장 높은 값 출력, 비어있으면 예외
# 기타
contains(Object o) : 포함여부확인, 포함되어있으면 true
isEmpty() : 비어있는지 확인
size() : 크기
전체 값 가져올때는 for문 혹은 Iterator 사용
우선순위 큐 (PriorityQueue) 정리
추가 : add(e), offer(e)
삭제 : poll(), remove(), remove(o)
출력 : peek(), element()
크기 : size()
포함확인 : contains(o)
비어있는지확인 : isEmpty()
Reference
https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90