1. 우선순위 큐 (Priority Queue)
ㅇ 임의 순서로 삽입되나 (입력/추가), 일정 순서로 삭제됨 (출력/제거)
- 입력은, 임의 순서이나,
- 출력은, 반드시 일정/정해준 순서를 갖음
2. 우선순위 큐의 기준
ㅇ 내림차순 우선순위 큐 (Descending Priority Queue)
- 항상 제일 큰 항목부터 우선 삭제 (키 값이 클수록 높은 우선순위)
ㅇ 오름차순 우선순위 큐 (Ascending Priority Queue)
- 항상 제일 작은 항목부터 우선 삭제 (키 값이 작을수록 높은 우선순위)
3. 우선순위 큐의 구현 방법
ㅇ 이진 힙을 이용한 구현
ㅇ 피보나치 힙을 이용한 구현
ㅇ 배열을 이용한 구현
4. 우선순위 큐의 연산들
ㅇ create() : 우선순위 큐 생성
ㅇ initialize(q) : 우선순위 큐 q를 초기화
ㅇ insert(q, a) : 우선순위 큐 q에 요소 a를 추가
ㅇ delete(q) : 우선순위 큐 q 중 가장 우선순위가 높은 요소를 삭제하고, 이 요소를 반환
- deleteMax(), deleteMin()
ㅇ find(q), peek(q) : 우선순위 큐 q 중 우선순위가 가장 높은 요소를 찾아 반환
5. 우선순위 큐의 용도
※ (주로, 여러 항목 중 최소값/최대값을 찾아야 하는 경우)
ㅇ 최단 경로 알고리즘 (다익스트라 알고리즘)
ㅇ 최소 신장 트리 알고리즘 (프림 알고리즘)
ㅇ 데이터 압축 (허프만 코딩)
ㅇ 정렬 알고리즘 등