Topic 11 · Heap
Heap Deletion — Heapify Down
Heap থেকে delete মানে সবসময় root delete। তিনটা ধাপ মুখস্থ করলেই হবে:
root সরাও → শেষের element কে root এ আনো → নিচে নামাও।
১. প্রশ্ন (Question)
EXAM QUESTION
(a) নিচের Max Heap থেকে root delete করো এবং প্রতিটি ধাপ (array + tree) দেখাও:
80, 75, 50, 62, 42, 35, 29, 15, 47
(b) ফলাফল থেকে আরও একবার root delete করো।
(c) Min Heap 10, 20, 30, 40, 50, 60, 70 থেকে root delete করো।
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ Index এর নিয়ম (1-based)
Heap কে array তে রাখা হয়। index
i এর জন্য —
Left child = 2i
Right child = 2i + 1
Parent = i / 2 (ভাগশেষ বাদ দিয়ে, floor)
কেন দরকার: Heapify down এ প্রতিবার "আমার দুইটা child কোথায়?" জানতে হয় —
এই সূত্র ছাড়া এক ধাপও এগোনো যায় না। খাতায় প্রতিটা ধাপে index লিখলে ভুল হওয়ার
সুযোগ কমে যায়।
0-based হলে: left =
2i+1, right =
2i+2, parent =
(i−1)/2।
প্রশ্নে বলা না থাকলে
1-based ব্যবহার করো এবং খাতায় লিখে দাও।
২.২ Heap Property
Max Heap: প্রতিটা parent তার child দের চেয়ে বড় বা সমান (parent ≥ child)।
Min Heap: প্রতিটা parent তার child দের চেয়ে ছোট বা সমান (parent ≤ child)।
কেন দরকার: Max heap এ সবচেয়ে বড় value সবসময় root এ থাকে — তাই delete করলে
সবসময় সবচেয়ে বড়টাই বের হয়। এটাই priority queue এর মূল কাজ।
২.৩ Complete Binary Tree
Heap সবসময় complete binary tree — প্রতিটা level বাম থেকে ডানে সম্পূর্ণ ভরা,
শুধু শেষ level ডান দিক থেকে খালি থাকতে পারে।
কেন এটাই delete এর নিয়ম ঠিক করে দেয়: root মুছে ফেললে গাছে ফাঁক তৈরি হয়। ফাঁক
পূরণ করতে শেষ element কেই আনতে হবে, কারণ ওটা সরালেই গাছটা complete থাকে।
মাঝখানের কাউকে সরালে ফাঁক থেকে যেত।
২.৪ Heapify Down (Sink / Percolate Down)
একটা node কে তার সঠিক জায়গায় নিচে নামিয়ে নেওয়ার প্রক্রিয়া। প্রতি ধাপে —
node কে তার দুই child এর মধ্যে বড়টার (min heap হলে ছোটটার) সাথে তুলনা করা হয়,
প্রয়োজন হলে swap হয়, তারপর নিচের level এ গিয়ে একই কাজ।
কেন "বড়টার" সাথেই: ছোট child এর সাথে swap করলে ওই ছোট child উপরে উঠে যেত,
আর তখন সে তার ভাইয়ের (বড় child এর) চেয়ে ছোট হয়ে যেত — heap property আবার ভেঙে যেত।
তাই সবসময় বড় child কেই উপরে তুলতে হয়।
২.৫ Insertion এর সাথে পার্থক্য
| বিষয় | Insertion | Deletion |
|---|
| নতুন element কোথায় বসে | শেষে | শেষেরটা root এ ওঠে |
| কোন দিকে যায় | Bubble Up (উপরে) | Heapify Down (নিচে) |
| কার সাথে তুলনা | Parent (একজন) | দুই child এর বড়টা |
| Complexity | O(log n) | O(log n) |
কেন মনে রাখা জরুরি: পরীক্ষায় দুইটাই একসাথে আসে। উল্টাপাল্টা করলে পুরো উত্তর ভুল।
৩. Exam Definition (English)
Heap Deletion: In a heap, deletion always removes the root element — the maximum in a
max heap and the minimum in a min heap. The root is removed, the last element of the heap is moved
into the root position, and the heap size is reduced by one. The new root is then restored to a
valid position by the heapify-down (sink) operation: it is repeatedly compared with the
larger of its two children (the smaller, in a min heap) and swapped with that child whenever the
heap property is violated, until it reaches a position where the property holds or it becomes a
leaf.
Complexity: O(log n), since the element travels at most the height of the
tree, which is ⌊log₂ n⌋.
৪. Concept Explanation (বাংলায়)
Heap থেকে delete মানে শুধু root delete — মাঝখান থেকে যেকোনো একজনকে তুলে নেওয়া
heap এর কাজ নয়। কারণ heap এর একমাত্র প্রতিশ্রুতি হলো "সবচেয়ে বড়টা (বা ছোটটা) আমি
সবসময় হাতের কাছে রাখব"।
Root তুলে নিলে উপরে একটা ফাঁকা চেয়ার তৈরি হয়। এখন প্রশ্ন — কে বসবে?
উত্তর: একদম শেষের element। কারণ ওকে সরালে গাছটা এখনো complete থাকে।
কিন্তু শেষের element সাধারণত সবচেয়ে ছোটদের একজন — তাকে root এ বসালে heap property
ভেঙে যাবে। তাই তাকে নিচে নামিয়ে সঠিক জায়গায় নিয়ে যেতে হবে। প্রতি ধাপে সে
তার দুই সন্তানের দিকে তাকায়, যে বড় তার সাথে জায়গা বদল করে, আর এক ধাপ নিচে নামে।
যতক্ষণ না সে তার দুই সন্তানের চেয়ে বড় হয়ে যায়, অথবা নিচে আর কেউ না থাকে — ততক্ষণ চলে।
এক লাইনে: "Root ফেলো → শেষেরটা উপরে আনো → বড় child এর সাথে swap করতে করতে নামাও।"
৫. Algorithm (English)
DELETE_MAX(A, n) // A is 1-based, n = heap size
if n == 0 then
return "heap is empty"
max = A[1] // the value being deleted
A[1] = A[n] // move the last element to the root
n = n - 1 // shrink the heap
HEAPIFY_DOWN(A, n, 1)
return max
HEAPIFY_DOWN(A, n, i)
while true do
largest = i
left = 2 * i
right = 2 * i + 1
if left <= n and A[left] > A[largest] then largest = left
if right <= n and A[right] > A[largest] then largest = right
if largest == i then
break // heap property satisfied — stop
swap A[i] and A[largest]
i = largest // continue from the new position
Min Heap এর জন্য: শুধু দুইটা > কে < করো এবং
largest এর বদলে smallest লেখো। বাকি সব হুবহু এক।
৬. ধাপে ধাপে ব্যাখ্যা (বাংলায়)
ধাপ ১ — Root এর value লিখে রাখো
এটাই delete হওয়া value (max heap এ সবচেয়ে বড়টা)।
কেন: প্রশ্নে প্রায়ই জিজ্ঞেস করা হয় "কোন value delete হলো" — এটাই উত্তর।
ধাপ ২ — শেষ element কে root এ আনো, size এক কমাও
Array এর একদম শেষ ঘরের value টা index 1 এ বসাও, তারপর heap size n থেকে n−1 করো।
কেন শেষেরটাই: complete binary tree তে শেষের node টাই একমাত্র node
যাকে সরালে গাছে ফাঁক তৈরি হয় না।
ধাপ ৩ — দুই child এর মধ্যে বড়টা বের করো
index i এর child হলো 2i আর 2i+1। খেয়াল রাখো index যেন heap size ছাড়িয়ে না যায়।
কেন size চেক করতে হয়: delete করার পর size কমে গেছে। পুরোনো size ধরে
হিসাব করলে মুছে ফেলা element কেই আবার তুলে আনবে — খুব সাধারণ ভুল।
ধাপ ৪ — দরকার হলে swap করে নিচে নামো
বর্তমান value ওই বড় child এর চেয়ে ছোট হলে swap করো এবং ওই child এর index এ চলে যাও।
কেন বড় child: ছোটটার সাথে swap করলে সে উপরে উঠে তার বড় ভাইয়ের
parent হয়ে যেত — heap property আবার ভাঙত।
ধাপ ৫ — কখন থামবে
দুইটার যেকোনো একটা হলেই থামো — (ক) বর্তমান value দুই child এর চেয়েই বড়, অথবা
(খ) নিচে আর কোনো child নেই (leaf এ পৌঁছে গেছ)।
কেন থামা নিরাপদ: heap property শুধু parent–child সম্পর্কেই লাগে।
একবার ঠিক হয়ে গেলে নিচের সব সম্পর্ক আগে থেকেই ঠিক ছিল, তাই আর কিছু করার নেই।
৭. শুরুর Heap
Index : 1 2 3 4 5 6 7 8 9
Array : 80 75 50 62 42 35 29 15 47
80 (1)
/ \
75 (2) 50 (3)
/ \ / \
62 (4) 42 (5) 35 (6) 29 (7)
/ \
15 (8) 47 (9)
যাচাই: 80 ≥ 75, 50 ✓ · 75 ≥ 62, 42 ✓ · 62 ≥ 15, 47 ✓ · 50 ≥ 35, 29 ✓ — বৈধ Max Heap।
Heap size n = 9।
৮. সমাধান — দুইবার Delete
(a) প্রথম Delete — root 80
ধাপ ১ : delete হওয়া value = 80
ধাপ ২ : শেষ element A[9] = 47 কে root এ আনো, n = 9 − 1 = 8
Index : 1 2 3 4 5 6 7 8
Array : 47 75 50 62 42 35 29 15
↑ এখন heap property ভাঙা (47 < 75)
ধাপ ৩ এর গুরুত্বপূর্ণ জায়গা: i = 4 এর right child হবে index 9। কিন্তু delete এর পর
heap size n = 8, তাই index 9 আর heap এর ভেতরে নেই। ওখানে পুরোনো 47 পড়ে থাকলেও সেটা
heap এর অংশ নয়। এই size চেকটা ভুলে গেলে উত্তর ভুল হয়ে যায়।
প্রথম delete এর পর:
Index : 1 2 3 4 5 6 7 8
Array : 75 62 50 47 42 35 29 15
75 (1)
/ \
62 (2) 50 (3)
/ \ / \
47 (4) 42 (5) 35 (6) 29 (7)
/
15 (8)
যাচাই: 75 ≥ 62, 50 ✓ · 62 ≥ 47, 42 ✓ · 47 ≥ 15 ✓ · 50 ≥ 35, 29 ✓ — বৈধ Max Heap।
(b) দ্বিতীয় Delete — root 75
ধাপ ১ : delete হওয়া value = 75
ধাপ ২ : শেষ element A[8] = 15 কে root এ আনো, n = 8 − 1 = 7
Index : 1 2 3 4 5 6 7
Array : 15 62 50 47 42 35 29
দ্বিতীয় delete এর পর:
Index : 1 2 3 4 5 6 7
Array : 62 47 50 15 42 35 29
62 (1)
/ \
47 (2) 50 (3)
/ \ / \
15 (4) 42 (5) 35 (6) 29 (7)
যাচাই: 62 ≥ 47, 50 ✓ · 47 ≥ 15, 42 ✓ · 50 ≥ 35, 29 ✓ — বৈধ Max Heap।
(c) Min Heap থেকে Delete
শুরুর Min Heap : 10 20 30 40 50 60 70 (n = 7)
10 (1)
/ \
20 (2) 30 (3)
/ \ / \
40 (4) 50 (5) 60 (6) 70 (7)
ধাপ ১ : delete হওয়া value = 10 (সবচেয়ে ছোট)
ধাপ ২ : শেষ element A[7] = 70 কে root এ আনো, n = 6
Array : 70 20 30 40 50 60
যাচাই: 20 ≤ 40, 30 ✓ · 40 ≤ 70, 50 ✓ · 30 ≤ 60 ✓ — বৈধ Min Heap।
খেয়াল করো: নিয়ম হুবহু একই, শুধু "বড়" এর জায়গায় "ছোট"।
৯. Final Exam Answer (English)
Max-heap deletion trace
Start : 80 75 50 62 42 35 29 15 47 (n = 9)
Delete 1 — removed value = 80
move 47 up : 47 75 50 62 42 35 29 15 (n = 8)
swap 47,75 : 75 47 50 62 42 35 29 15
swap 47,62 : 75 62 50 47 42 35 29 15 ← result
Delete 2 — removed value = 75
move 15 up : 15 62 50 47 42 35 29 (n = 7)
swap 15,62 : 62 15 50 47 42 35 29
swap 15,47 : 62 47 50 15 42 35 29 ← result
Min heap 10 20 30 40 50 60 70, delete 10
: 20 40 30 70 50 60 (n = 6)
Each deletion costs O(log n) — at most the height of the tree, ⌊log₂ n⌋ swaps
১০. Common Mistakes
- Root এর জায়গায় সরাসরি বড় child কে বসিয়ে দেওয়া — এতে গাছ আর complete থাকে না। নিয়ম হলো শেষ element কে উপরে আনা।
- ছোট child এর সাথে swap করা — সবসময় বড় child (min heap এ ছোট child) এর সাথে। নইলে property আবার ভাঙবে।
- Heap size কমাতে ভুলে যাওয়া — delete এর পর n এক কমে। পুরোনো n ধরে হিসাব করলে মুছে ফেলা element কেই আবার তুলে আনবে।
- Bubble Up আর Heapify Down গুলিয়ে ফেলা — Insert = উপরে (parent এর সাথে), Delete = নিচে (child দের সাথে)।
- প্রতি ধাপে শুধু একটা child দেখা — দুইটা child ই দেখতে হবে, তারপর বড়টা বাছতে হবে।
- মাঝখান থেকে delete করার চেষ্টা — heap এ delete মানে root delete। নির্দিষ্ট element মুছতে বললে আলাদা নিয়ম (নিচে দেখো)।
- শুধু শেষ array লেখা, ধাপ না দেখানো — প্রতিটা swap এর পরের array লেখাই নম্বরের জায়গা।
- Index না লেখা — কোন index থেকে কোথায় যাচ্ছ লিখে না দিলে examiner ধাপ অনুসরণ করতে পারে না।
বোনাস — নির্দিষ্ট কোনো element delete করতে বললে (root নয়):
১। ওই element এর index খুঁজে বের করো
২। শেষ element কে ওই জায়গায় বসাও, size এক কমাও
৩। এখন দুইটা সম্ভাবনা — নতুন value টা parent এর চেয়ে বড় হলে Bubble Up করো,
আর child দের চেয়ে ছোট হলে Heapify Down করো
কেন দুইটাই লাগতে পারে: root এ বসালে শুধু নিচে নামার সুযোগ থাকে, কিন্তু মাঝখানে বসালে
উপরে-নিচে দুই দিকেই যাওয়ার দরকার হতে পারে।
১১. Viva Questions
Q: Heap থেকে সবসময় root ই delete করা হয় কেন?
Q: Root delete করার পর শেষ element কেই উপরে আনা হয় কেন? অন্য কাউকে কেন নয়?
Q: Heapify down এ বড় child এর সাথেই swap করতে হয় কেন?
Q: Deletion এর time complexity কত এবং কেন O(log n)?
Q: Bubble Up আর Heapify Down এর পার্থক্য কী?
Q: Min heap এ delete করলে কোন value বের হয়?
Q: Heapify down কখন থামে — দুইটা শর্ত বলো।
Q: Heap থেকে সব element delete করতে থাকলে কী ক্রমে বের হবে? এটার নাম কী? (উত্তর: sorted ক্রমে — এটাই Heap Sort)
১২. Practice Questions
- Max Heap
80, 75, 50, 52, 42, 35 (n = 6) থেকে root delete করো।
উত্তর দেখাও
Delete 80। শেষ element 35 উপরে → 35 75 50 52 42 (n = 5)।
i=1: child 75, 50 → বড় 75; 35 < 75 swap → 75 35 50 52 42
i=2: child A[4]=52, A[5]=42 → বড় 52; 35 < 52 swap → 75 52 50 35 42
i=4: child A[8], A[9] নেই → থামো। উত্তর: 75 52 50 35 42
- Max Heap
100, 90, 70, 60, 50, 40, 30 থেকে পরপর দুইবার delete করো।
উত্তর দেখাও
প্রথম: delete 100; 30 উপরে → 30 90 70 60 50 40; swap 30↔90 → 90 30 70 60 50 40;
i=2 এর child 60, 50 → বড় 60; swap → 90 60 70 30 50 40
দ্বিতীয়: delete 90; 40 উপরে → 40 60 70 30 50; i=1 এর child 60, 70 → বড় 70; swap → 70 60 40 30 50;
i=3 এর child নেই → থামো। 70 60 40 30 50
ফাঁদ: দ্বিতীয় ধাপে বড় child ছিল ডানেরটা (70), বামেরটা (60) নয়।
- Min Heap
5, 15, 10, 25, 30, 20 থেকে root delete করো।
উত্তর দেখাও
Delete 5; শেষ element 20 উপরে → 20 15 10 25 30 (n = 5)।
i=1: child 15, 10 → ছোট 10; 20 > 10 swap → 10 15 20 25 30
i=3: child A[6], A[7] নেই → থামো। উত্তর: 10 15 20 25 30
- Max Heap এ শুধু একটা element থাকলে delete করলে কী হবে?
উত্তর দেখাও
Root ই শেষ element। সেটা মুছে দিলে n = 0, heap খালি হয়ে যায়। কোনো heapify লাগে না।
- Heap
90, 85, 70, 40, 60, 50, 20 থেকে 60 (root নয়) delete করো।
উত্তর দেখাও
60 আছে index 5 এ। শেষ element A[7] = 20 কে index 5 এ বসাও → 90 85 70 40 20 50 (n = 6)।
Parent A[2] = 85 > 20 ✓ (bubble up লাগবে না), index 5 এর কোনো child নেই ✓ → কাজ শেষ।
উত্তর: 90 85 70 40 20 50
- একটা max heap থেকে পরপর সব element delete করলে কী ক্রমে বের হয়? এটা কোন sorting algorithm?
উত্তর দেখাও
বড় থেকে ছোট ক্রমে (descending)। এটাই
Heap Sort এর মূল ধারণা।
- HEAPIFY_DOWN এর pseudocode লেখো এবং কেন এর complexity O(log n) ব্যাখ্যা করো।
- 15 টা node এর একটা complete binary tree থেকে root delete করলে সর্বোচ্চ কয়টা swap লাগতে পারে?
উত্তর দেখাও
Height = ⌊log₂ 15⌋ = 3, তাই সর্বোচ্চ 3 টা swap।