टेलरों की छँटाई

हीप एक ऐसा संग्रह है जिसे हमेशा अपना सबसे छोटा आइटम पता रहता है और जो आपको वह आइटम जल्दी से बाहर निकालने देता है। यह प्राथमिकता कतार के लिए स्वाभाविक टूल है, यानी ऐसी कतार जिसमें सबसे ज़रूरी आइटम पहले निकाला जाता है, न कि वह जो सबसे ज़्यादा देर से इंतज़ार कर रहा हो। हीप 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 सिर्फ वैल्यू रखता है और की हटा देता है।