Heap — push ও pop-এর প্রতিটি পরিবর্তন

অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান

Min-heap-এ প্রতিটি parent তার child-দের চেয়ে ছোট বা সমান। Push বা pop-এর পরে এই নিয়ম ভাঙলে একটি পথ ধরে swap করেই ঠিক করি। নিচের tree আর array একই heap-এর দুই রূপ।

flowchart TD
  n0["index 0 · value 3"] --> n1["index 1 · value 5"]
  n0 --> n2["index 2 · value 4"]
  n1 --> n3["index 3 · value 9"]
  n1 --> n4["index 4 · value 6"]

Array-তে index i-এর parent (i−1)//2; children 2*i+1 ও 2*i+2। কোনো child index array-র বাইরে পড়লে সেই child নেই।

Push 1 — নিচ থেকে উপরে ঠিক করা

নতুন value সবশেষে বসালে tree-এর complete shape ঠিক থাকে। তারপর parent-এর সঙ্গে তুলনা করি। প্রতিটি ধাপে highlight করা বাক্সে তুলনা বা swap হচ্ছে।

Sift up — 1-এর root পর্যন্ত ওঠা

1. শুরুর heap

   03

   15

   24

   39

   46

   প্রতিটি parent তার child-এর চেয়ে ছোট বা সমান।

2. ১. শেষে 1 যোগ

   03

   15

   চিহ্নিত ঘর: 24↑ parent

   39

   46

   চিহ্নিত ঘর: 51↑ new

   Index 5-এর parent index 2। 1 < 4, তাই swap লাগবে।

3. ২. 4-এর সঙ্গে swap

   চিহ্নিত ঘর: 03↑ parent

   15

   চিহ্নিত ঘর: 21↑ new

   39

   46

   54

   1 এখন index 2-এ। তার নতুন parent 3; 1 < 3।

4. ৩. 3-এর সঙ্গে swap; শেষ

   চিহ্নিত ঘর: 01↑ root

   15

   23

   39

   46

   54

   1 root-এ পৌঁছেছে। আর parent নেই; মোট দুইটি swap।

চলার পথ index 5 → 2 → 0। Heap-এর অন্য শাখার 5, 9 ও 6 একবারও সরেনি। Parent ছোট বা সমান হয়ে গেলেও আগে থেমে যেতাম; সব push-এ root পর্যন্ত উঠতে হয় না।

Pop minimum — উপর থেকে নিচে ঠিক করা

Root-এর 1 হলো ফেরত দেওয়ার উত্তর। শেষ value 4-কে root-এ এনে শেষ slot বাদ দিই। এভাবে shape ঠিক থাকে, কিন্তু root-এর value ঠিক জায়গায় নাও থাকতে পারে।

Sift down — minimum 1 সরানোর পরে

1. ১. শেষ value root-এ

   চিহ্নিত ঘর: 04↑ root

   চিহ্নিত ঘর: 15

   চিহ্নিত ঘর: 23

   39

   46

   Children 5 ও 3-এর মধ্যে ছোটটি 3। 4 > 3, তাই 3-এর সঙ্গে swap।

2. ২. ছোট child-এর সঙ্গে swap

   চিহ্নিত ঘর: 03

   15

   চিহ্নিত ঘর: 24↑ moved

   39

   46

   4 এখন index 2-এ। Child index 5 ও 6 array-র বাইরে, তাই শেষ।

ছোট child কেন বেছে নিই? উপরে ওঠা value-টি দুই child-এরই parent হবে। 5-কে তুললে তার নিচে 3 থেকে যায়; 5 ≤ 3 সত্য নয়। 3-কে তুললেই দুই দিকের নিয়ম মেলে।

আবার pop — এবার উত্তর 3

দ্বিতীয় pop-এর সম্পূর্ণ পরিবর্তন

1. ১. 3 সরিয়ে শেষের 6 root-এ

   চিহ্নিত ঘর: 06

   চিহ্নিত ঘর: 15

   চিহ্নিত ঘর: 24

   39

   Children 5 ও 4; ছোট child হলো 4।

2. ২. 4-এর সঙ্গে swap; শেষ

   চিহ্নিত ঘর: 04

   15

   চিহ্নিত ঘর: 26

   39

   6-এর আর child নেই। Heap আবার ঠিক আছে।

দুই pop-এ বের হলো 1, তারপর 3। Min-heap থেকে সব value pop করলে ছোট থেকে বড় ক্রমে পাই। n বার pop-এর মোট সময় O(n log n); এটি heap ব্যবহার করে sorting করার একটি পদ্ধতি।

কোন repair কখন লাগে

প্রশ্ন	Sift up	Sift down
কখন	Push-এর পরে	Root pop করার পরে
শুরু	নতুন শেষ slot	শেষ value দিয়ে পূরণ করা root
তুলনা	নিজের parent	নিজের দুই child-এর ছোটটি
দিক	Root-এর দিকে	Leaf-এর দিকে
থামার শর্ত	Parent ছোট বা সমান; অথবা root	Children বড় বা সমান; অথবা leaf
সর্বোচ্চ ধাপ	Tree height: O(log n)	Tree height: O(log n)

নিজে চেষ্টা করো

1. [3, 5, 4, 9, 6]-এ 0 push করলে দুইটি swap কোথায় হবে?
2. একই heap-এ 7 push করলে কেন কোনো swap লাগবে না?
3. [2, 5, 3, 9, 6, 8, 4] থেকে দুইবার pop করে প্রতিবারের array লেখো।
4. [9, 4, 7, 1, 3]-এ heapify করো: আগে index 1, তারপর index 0-তে sift down। মূল ব্যাখ্যার trace-এর সঙ্গে মিলিয়ে দেখো।

চলমান tree দেখতে VisuAlgo-এর Binary Heap ব্যবহার করতে পারো।