টেলারদের ট্রায়াজ

একটি হিপ হলো এমন একটি কালেকশন, যা সব সময় তার সবচেয়ে ছোট আইটেমটি জানে এবং আপনাকে সেটি দ্রুত বের করে নিতে দেয়। প্রায়োরিটি কিউ-এর স্বাভাবিক হাতিয়ার এটি, অর্থাৎ এমন একটি অপেক্ষার সারি যেখানে সবচেয়ে গুরুত্বপূর্ণ আইটেমটিই সবার আগে আসে, সবচেয়ে দীর্ঘক্ষণ অপেক্ষা করা আইটেমটি নয়। হিপ থাকে heaps ভোকাবুলারিতে।

একটি হিপ তৈরি করা

<min-heap> একটি খালি হিপ তৈরি করে, যার সবচেয়ে ছোট কী (key) সবার আগে বেরিয়ে আসে; আর <max-heap> হলো তার ঠিক উল্টো।

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

আইটেম যোগ করা

প্রতিটি আইটেম একটি মান এবং একটি কী (key) হিসেবে একসাথে জমা থাকে। এই কী (key)-ই হলো সেই প্রায়োরিটি, যার ভিত্তিতে 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 সামনের আইটেমটি, অর্থাৎ সবচেয়ে ছোট কী (key)-ওয়ালা মানটি, না সরিয়েই ফিরিয়ে দেয়। 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 শুধু মানগুলো রাখে, কী (key)গুলো ফেলে দেয়।