تریاژ صندوق‌دارها

«کپه» مجموعه‌ای است که همیشه کوچک‌ترین عنصرش را می‌شناسد و به شما اجازه می‌دهد آن عنصر را به‌سرعت بیرون بیاورید. این ابزار طبیعی برای یک «صف اولویت» است، یعنی صفی که در آن نوبت به مهم‌ترین عنصر می‌رسد، نه به عنصری که بیشتر از همه منتظر مانده است. کپه‌ها در واژگان 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 یک لیست انجمنی هستند: values (در assocs) فقط مقدارها را نگه می‌دارد و کلیدها را دور می‌ریزد.