Module ৭ · priority_queue: সবচেয়ে বড়টা আগে বেরোয়
ভেতরের কথা: vector-এর ভেতরের heap, sift-এর হিসাব আর make_heap
Proপড়া
Kenji-র lab-এর scheduler তার maintenance task-গুলো pointer-এর একটা priority_queue-তে রাখে। Mouse-টা গোলমাল শুরু করলে ও pointer দিয়েই সেটার urgency 2 থেকে বাড়িয়ে 9 করে দেয়। তবু পরের pop-গুলো mouse-এর আগে printer (7) আর projector (6)-কেই বের করে। Maria ঠিক সেই প্রশ্নটা করে, যার উত্তর এই lesson: "কিন্তু heap টের পেল না কেন?" কারণটা দেখতে চলো heap-টা খুলে ওর vector-টা পড়ি।
আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…
ভেতরের কথা: vector-এর ভেতরের heap, sift-এর হিসাব আর make_heap এর ভেতরে কী আছে
- priority_queue মানে একটা vector আর heap-এর তিনটা call
- Tree আসলে slot নম্বরের অঙ্ক
- Push উপরে ওঠে, pop একটা hole নিচে পাঠায়
- O(n)-এ make_heap: বেশির ভাগ slot থাকে নিচের দিকে
- কেন erase, decrease-key আর iterator নেই
- Memory-তে খরচ কত
- Performance lab