부산대학교자료구조
Scientific Inference Lab

The Smallest One First

Priority Queue ADT

우선순위 큐(priority queue)는 값을 넣고, 그 가운데 가장 작은 값을 찾고 꺼내는 세 연산을 갖춘 ADT다. 도착한 차례가 아니라 우선순위 규칙이 꺼낼 원소를 정하며, ADT는 연산만 정할 뿐 값을 어떻게 담을지는 정하지 않는다.

세 연산넣기(add, heappush), 최솟값 보기(find_min, h[0]), 최솟값 꺼내기(remove, heappop)다.
지정 삭제는 없다사용자가 "7을 꺼내라"고 고를 수 없고, 꺼낼 원소는 우선순위 규칙이 정한다.
쓰이는 곳작업 스케줄링의 급한 일, 응급실의 위중한 환자, 인쇄 작업 중 쪽수가 적은 것처럼 우선순위가 높은 대상을 먼저 고른다.
구현별 연산 비용배열 구현은 삽입이나 최솟값 삭제 중 하나가 O(n)이고, 힙은 두 연산 모두 O(log n)이다.

넣은 순서와 상관없이 꺼낼 때마다 현재 최솟값이 나온다

7, 3, 12, 1, 9를 넣은 뒤 최솟값을 보고 꺼내는 요청을 차례로 처리한다. 처리한 요청 수를 바꾸면 담긴 값, 현재 최솟값, 꺼낸 값의 줄이 바뀐다.

우선순위 큐의 요청 처리요청 목록, 담긴 값, 꺼낸 값
왼쪽 목록은 요청의 순서이고 초록 칸이 방금 처리한 요청이다. 가운데 점선 영역은 담긴 값이며 안쪽 순서는 의미가 없다. 초록으로 채운 원이 현재 최솟값, 초록 테두리 원이 방금 넣은 값이다. 아래 초록 칸은 꺼낸 값을 꺼낸 순서대로 적은 것이다.

배열로 만들면 넣기와 꺼내기 가운데 한쪽이 전체를 훑거나 밀어야 한다

같은 요청을 정렬 안 한 배열과 내림차순으로 정렬한 배열(최솟값이 맨 끝)에서 처리한다. 처리한 요청 수를 바꾸면 두 배열의 내용과 이번 요청에서 살펴보거나 옮긴 칸이 바뀐다.

두 배열 구현의 비용정렬 안 한 배열과 정렬된 배열이 이번 요청에서 다룬 칸
두 줄이 두 구현의 배열이다. 초록 칸은 이번 요청에서 값을 비교하려고 살펴보거나 자리를 옮긴 칸이고, 파란 칸은 그대로 있는 값이다. 오른쪽 수는 이번 요청의 칸 수와 지금까지의 합이다.

원소 수가 커질수록 O(n) 연산 하나가 전체 비용을 좌우한다

원소 수 n을 바꾸면 네 구현에서 넣기 한 번과 최솟값 꺼내기 한 번에 드는 대략의 단계 수가 바뀐다. BST는 평균적인 경우의 연산 비용을 표시한다.

구현별 연산 비용넣기와 최솟값 꺼내기의 단계 수
가로 막대의 길이는 로그 눈금이라 눈금 하나가 10배다. 위쪽 파란 막대가 넣기, 아래쪽 초록 막대가 최솟값 꺼내기의 단계 수다.