Heap — Visual Explanation¶

দুটো repair — sift-up আর sift-down — frame by frame দেখো, tree view আর array view দুটোতেই।

প্রতিটা heap operation আসলে "সস্তা structural কাজটা করো, তারপর একটা path ধরে heap property repair করো।" এই file টা একটা ছোট min-heap-এর উপর দুটো repair-ই trace করে। প্রতিটা frame pencil দিয়ে follow করো; goal হলো পরের frame পড়ার আগেই swap-গুলো predictable হয়ে যাওয়া।

Part 1 — Push 1: append, তারপর sift up¶

শুরুর min-heap (valid: প্রতিটা parent <= তার children):

Tree:            3              Array: [3, 5, 4, 9, 6]
               /   \                    0  1  2  3  4
             5       4
            / \
           9   6

আমরা 1 value-টা push করব।

Frame 1 — শেষে append করো (tree complete রাখো)¶

                 3              Array: [3, 5, 4, 9, 6, 1]
               /   \                    0  1  2  3  4  5
             5       4
            / \     /
           9   6   1   <- new node at index 5

Tree এখনো complete, কিন্তু heap property ভেঙে গেছে: parent 4 (index 2) তার child 1 (index 5)-এর চেয়ে বড়।

Frame 2 — parent-এর সাথে compare করো, ছোট হলে swap¶

Index 5-এর parent হলো (5-1)//2 = 2, value 4। যেহেতু 1 < 4, swap।

                 3              Array: [3, 5, 1, 9, 6, 4]
               /   \                    0  1  2  3  4  5
             5       1   <- 1 bubbled up
            / \     /
           9   6   4

Frame 3 — উঠতেই থাকো¶

Index 2-এর parent হলো (2-1)//2 = 0, value 3। যেহেতু 1 < 3, swap।

                 1   <- new root  Array: [1, 5, 3, 9, 6, 4]
               /   \                      0  1  2  3  4  5
             5       3
            / \     /
           9   6   4

Frame 4 — থামো¶

Index 0-এর কোনো parent নেই। শেষ। Bubble-টা একটা root-মুখী path ধরে উঠল: 6-টা item-এর জন্য 2-টা swap — কখনোই tree height-এর (~log n) বেশি না।

Mental movie: পানির ভেতর দিয়ে একটা bubble উঠছে। এটা সবসময় সোজা উপরে যায়, প্রতি comparison-এ এক level, আর উপরের পানি হালকা হওয়া মাত্র থেমে যায়।

Part 2 — Minimum-টা pop করো: swap-to-end, তারপর sift down¶

মাত্র যে heap টা বানালাম, সেখান থেকেই continue:

                 1              Array: [1, 5, 3, 9, 6, 4]
               /   \
             5       3
            / \     /
           9   6   4

আমরা pop করি। উত্তরটা obviously 1 (root) — আসল কাজ হলো ওটা যে গর্ত রেখে যায় সেটা repair করা।

Frame 1 — root save করো, LAST item টাকে root slot-এ আনো¶

শেষ item কেন? শেষ array slot remove করাই একমাত্র removal যেটা tree-কে complete রাখে।

   popped: 1
                 4   <- 4 teleported from the end   Array: [4, 5, 3, 9, 6]
               /   \                                        0  1  2  3  4
             5       3
            / \
           9   6

Root-এ heap property ভাঙা: 4 তার child 3-এর চেয়ে বড়।

Frame 2 — দুই child-এর সাথেই compare করো, ছোটটার সাথে swap¶

Index 0-এর children: index 1 (value 5) আর index 2 (value 3)। Smaller child হলো 3। যেহেতু 4 > 3, swap।

ছোট child-টার সাথেই কেন? কারণ যে উপরে উঠবে সে অন্য child-টারও parent হয়ে যাবে — শুধু ছোটটারই দুজনের উপরে বসার অনুমতি আছে।

                 3              Array: [3, 5, 4, 9, 6]
               /   \                    0  1  2  3  4
             5       4   <- 4 sank one level
            / \
           9   6

Frame 3 — ডুবতেই থাকো¶

Index 2-এর (value 4) children: 2*2+1 = 5 আর 2*2+2 = 6 — দুটোই array-র শেষ ছাড়িয়ে। কোনো child নেই, মানে 4 এখন একটা leaf। থামো।

                 3              Array: [3, 5, 4, 9, 6]   VALID HEAP
               /   \
             5       4
            / \
           9   6

Mental movie: একটা পাথর ডুবছে। প্রতিটা level-এ সে তার দুই child-এর দিকে তাকায়, হালকাটাকে বেছে নিয়ে swap করে, আর দুজনই ভারী হলে (বা নিচে পৌঁছে গেলে) থেমে যায়।

Part 3 — আরেকটা pop, দুই-ধাপের ডোবা দেখার জন্য¶

[3, 5, 4, 9, 6] থেকে আবার pop করো। উত্তর: 3। শেষ item 6 root-এ teleport করে।

Frame A:           6            Array: [6, 5, 4, 9]
                 /   \
               5       4
              /
             9

Frame B: children of 6 are 5 and 4 -> smaller is 4 -> swap.

                   4            Array: [4, 5, 6, 9]
                 /   \
               5       6
              /
             9

Frame C: 6 is now at index 2; children would be at 5 and 6 -> none. Stop.

দুটো pop-এ পেলাম 1, তারপর 3 — values গুলো sorted order-এ বেরোচ্ছে। সব n-টা item pop করাই ঠিক heapsort: n-টা pop, প্রত্যেকটা O(log n) — মোট O(n log n)।

দুই repair-এর ভেতরের pattern¶

	Sift up (after push)	Sift down (after pop)
শুরু হয়	শেষ slot-এ (new item)	root-এ (relocated item)
compare করে	1-টা parent-এর সাথে	2-টা children-এর সাথে (ছোটটাকে নেয়)
move করে	root-এর দিকে	leaves-এর দিকে
থামে যখন	parent ছোট-বা-সমান, বা root-এ পৌঁছালে	দুই children বড়-বা-সমান, বা leaf-এ পৌঁছালে
Max steps	tree height ~ log n	tree height ~ log n

দুটো repair-ই tree-র একটামাত্র path ছোঁয় — এই locality-টাই heap fast হওয়ার পুরো কারণ।

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

[3, 5, 4, 9, 6]-এ 0 push করো। আঁকার আগে প্রতিটা swap predict করো। (এটার একদম root পর্যন্ত ওঠার কথা।)
একই heap-এ 7 push করো। (এটার একদমই না নড়ার কথা — একটা comparison, শূন্য swap।)
[2, 5, 3, 9, 6, 8, 4] থেকে দুবার pop করো আর প্রতিটা pop-এর পরের array লেখো।
Unsorted array [9, 4, 7, 1, 3] নাও আর হাতে heapify চালাও: index 1 sift down করো, তারপর index 0। concept.md-র dry run-এর সাথে মিলিয়ে দেখো।

ঠিক এই animation-গুলোর একটা interactive version-এর জন্য VisuAlgo-র Binary Heap module টা try করো।