مقدمة
الكومة مجموعة تعرف دائمًا أصغر عنصر فيها، وتتيح لك إخراج ذلك العنصر سريعًا. إنها الأداة الطبيعية لطابور الأولوية: صف انتظار يُخدَم فيه العنصر الأهم تاليًا، لا العنصر الذي انتظر أطول مدة. توجد الأكوام في مفردات 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 تغيّرها في مكانها بدل أن تُرجع كومة جديدة. وkeep مفيدة لاستعادة الكومة إلى المكدس بعد أن تستهلكها heap-push.
النظر إلى المقدمة وإزالتها
تُرجع 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) تُبقي القيم فقط وتُسقط المفاتيح.
التعليمات
يخدم بنك مزدحم العملاء المنتظرين حسب الأولوية لا حسب ترتيب وصولهم. يحصل كل عميل على رقم أولوية عند أخذ تذكرة، ويخدم أمين الصندوق دائمًا صاحب الرقم الأصغر تاليًا (1 هو الأكثر إلحاحًا). والكومة الصغرى هي طابور الانتظار الأمثل.
1. افتح الطابور
عرّف new-queue، وهي لا تأخذ شيئًا وتُرجع طابور أولوية جديدًا فارغًا.
new-queue
! => an empty priority queue
2. أضف عميلًا
عرّف join-queue، وهي تأخذ اسم عميل ورقم أولوية وطابورًا. تضيف العميل إلى الطابور وتُرجع الطابور، بحيث يمكن إضافة العملاء واحدًا بعد الآخر.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
! => the queue, now holding alice (5) and bob (2)
3. من التالي؟
عرّف next-name، وهي تأخذ طابورًا وتُرجع اسم العميل الذي ينبغي خدمته تاليًا، أي صاحب أصغر رقم أولوية، دون إزالته.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue next-name .
! => "bob"
4. اخدم الجميع
عرّف serve-all، وهي تأخذ طابورًا وتُرجع أسماء جميع العملاء المنتظرين، بالترتيب الذي ستُخدم به.
new-queue "alice" 5 rot join-queue "bob" 2 rot join-queue
"carol" 9 rot join-queue serve-all .
! => { "bob" "alice" "carol" }
تمرين تعلّمي
