창구 직원의 분류

힙은 항상 가장 작은 항목이 무엇인지 알고 있고, 그 항목을 빠르게 꺼낼 수 있는 컬렉션이에요. 우선순위 큐에 딱 맞는 도구죠. 우선순위 큐는 가장 오래 기다린 항목이 아니라 가장 중요한 항목이 먼저 처리되는 대기 줄이에요. 힙은 heaps 보캐뷸러리에 들어 있어요.

힙 만들기

<min-heap>은 가장 작은 키가 먼저 나오는 빈 힙을 만들어요. <max-heap>은 그 반대고요.

<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )

항목 추가하기

각 항목은 값과 키를 함께 묶어 저장해요. 키는 Factor가 순서를 정할 때 기준으로 삼는 우선순위예요. heap-push로 항목 하나를 추가해요.

heap-push ( value key heap -- )

USING: heaps ;

<min-heap>
"alice" 5 pick heap-push   ! value "alice", priority 5
"bob"   2 pick heap-push   ! value "bob",   priority 2

힙은 변경 가능해요. heap-push는 새 힙을 반환하는 대신 원래 힙을 그 자리에서 바꿔요. heap-push가 힙을 소비한 뒤에 힙을 다시 스택에 올려놓고 싶을 때 keep이 편리해요.

맨 앞 항목 살펴보고 꺼내기

heap-peek은 맨 앞 항목, 즉 키가 가장 작은 값을 제거하지 않고 반환해요. heap-pop은 그 항목을 반환하면서 제거도 하고요. heap-empty?는 남은 항목이 있는지 알려줘요. 언제 꺼내기를 멈춰야 하는지 알 수 있죠. heap-pop-all은 모든 항목을 한 번에 제거하고, 우선순위 순서대로 { key value } 쌍의 연관 리스트를 반환해요.

heap-peek    ( heap -- value key )
heap-pop     ( heap -- value key )
heap-empty?  ( heap -- ? )
heap-pop-all ( heap -- alist )

USING: assocs heaps kernel prettyprint ;

<min-heap>
"alice" 5 pick heap-push
"bob"   2 pick heap-push
dup heap-empty? .        ! => f      (two items waiting)
dup heap-peek drop .     ! => "bob"  (smallest key, still in the heap)
dup heap-pop drop .      ! => "bob"  (smallest key, now removed)
heap-pop-all .           ! => { { 5 "alice" } }

heap-pop과 heap-empty?는 항목을 하나씩 처리할 때 쓰는 기본 재료예요. 맨 앞을 살펴보거나 꺼내서 필요한 작업을 하고, heap-empty?가 t를 반환하면 멈춰요. 아래 과제에서는 heap-pop-all로 큐 전체를 한 번에 비우지만, 힙이 빌 때까지 꺼내도 같은 순서가 나와요.

heap-pop-all이 돌려주는 쌍은 연관 리스트예요. assocs에 있는 values를 쓰면 키는 버리고 값만 남길 수 있어요.