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

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

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

```mermaid
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 হচ্ছে।

```dsa
kind: array
title: Sift up — 1-এর root পর্যন্ত ওঠা
steps:
  - label: শুরুর heap
    values: [3, 5, 4, 9, 6]
    note: প্রতিটি parent তার child-এর চেয়ে ছোট বা সমান।
  - label: ১. শেষে 1 যোগ
    values: [3, 5, 4, 9, 6, 1]
    active: [2, 5]
    pointers: {parent: 2, new: 5}
    note: Index 5-এর parent index 2। 1 < 4, তাই swap লাগবে।
  - label: ২. 4-এর সঙ্গে swap
    values: [3, 5, 1, 9, 6, 4]
    active: [0, 2]
    pointers: {parent: 0, new: 2}
    note: 1 এখন index 2-এ। তার নতুন parent 3; 1 < 3।
  - label: ৩. 3-এর সঙ্গে swap; শেষ
    values: [1, 5, 3, 9, 6, 4]
    active: [0]
    pointers: {root: 0}
    note: 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 ঠিক জায়গায় নাও থাকতে পারে।

```dsa
kind: array
title: Sift down — minimum 1 সরানোর পরে
steps:
  - label: ১. শেষ value root-এ
    values: [4, 5, 3, 9, 6]
    active: [0, 1, 2]
    pointers: {root: 0}
    note: Children 5 ও 3-এর মধ্যে ছোটটি 3। 4 > 3, তাই 3-এর সঙ্গে swap।
  - label: ২. ছোট child-এর সঙ্গে swap
    values: [3, 5, 4, 9, 6]
    active: [0, 2]
    pointers: {moved: 2}
    note: 4 এখন index 2-এ। Child index 5 ও 6 array-র বাইরে, তাই শেষ।
```

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

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

```dsa
kind: array
title: দ্বিতীয় pop-এর সম্পূর্ণ পরিবর্তন
steps:
  - label: ১. 3 সরিয়ে শেষের 6 root-এ
    values: [6, 5, 4, 9]
    active: [0, 1, 2]
    note: Children 5 ও 4; ছোট child হলো 4।
  - label: ২. 4-এর সঙ্গে swap; শেষ
    values: [4, 5, 6, 9]
    active: [0, 2]
    note: 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](concept.md)-এর সঙ্গে মিলিয়ে দেখো।

চলমান tree দেখতে [VisuAlgo-এর Binary Heap](https://visualgo.net/en/heap) ব্যবহার করতে পারো।