A Max Heap is given in array (1-based indexing) form as:
75, 62, 50, 47, 42, 35, 29, 15 (size = 8)
Insert the element 80 into this heap. Show the resulting heap after insertion, and show every step of the Bubble-Up (Heapify-Up) process, including the array and the compare/swap operations.
2. Prerequisite Concepts (বাংলায়)
2.1 Heap কী?
Heap হলো একটি বিশেষ ধরনের Complete Binary Tree, যেখানে প্রতিটি node একটি নির্দিষ্ট নিয়ম (heap property) মেনে চলে। Heap সাধারণত Array দিয়ে represent করা হয় — আলাদা করে pointer বা linked structure লাগে না, কারণ tree টা "complete" হওয়ায় index দিয়েই parent-child সম্পর্ক বের করা যায়।
2.2 Complete Binary Tree — কেন দরকার?
Complete Binary Tree মানে: শেষ level ছাড়া বাকি সব level সম্পূর্ণ ভরাট থাকবে, আর শেষ level ভরাট হবে বাম দিক থেকে।
কেন দরকার: Heap-কে array দিয়ে represent করতে হলে tree-টা অবশ্যই "gap-free" হতে হবে। যদি tree-তে ফাঁকা জায়গা থাকে (incomplete), তাহলে array-index দিয়ে parent/child বের করার formula আর কাজ করবে না। এই জন্যই insert করার সময় নতুন element সবসময় array-এর একদম শেষে বসানো হয় — এতে completeness নষ্ট হয় না।
2.3 Max Heap Property
Max Heap-এ নিয়ম হলো: parent ≥ child — অর্থাৎ প্রতিটি parent node তার দুই child-এর চেয়ে বড় অথবা সমান হবে। এর ফলে সবচেয়ে বড় element সবসময় root-এ থাকে।
কেন দরকার: এই property-র কারণেই আমরা O(1) সময়ে সবচেয়ে বড় element খুঁজে পাই (শুধু root দেখলেই হয়)। কিন্তু insert বা delete করার পর এই property ভেঙে যেতে পারে, তাই সেটা আবার ঠিক করতে হয় — এটাই "heapify" করার কারণ।
2.4 Array Indexing Formula (1-based) — কেন গুরুত্বপূর্ণ?
Heap-কে array-তে রাখলে node-এর index দিয়েই তার parent ও child বের করা যায়। Sir-এর নিয়ম অনুযায়ী (1-based indexing, অর্থাৎ array-এর প্রথম element index 1 থেকে শুরু):
Node index i হলে:
Left child = 2i
Right child = 2i + 1
Parent = i / 2 (floor / integer division)
কেন দরকার: Bubble-up বা heapify-down করার সময় বারবার parent-child খুঁজতে হয়। এই formula ছাড়া আমরা efficient ভাবে move করতে পারতাম না। পরীক্ষার খাতায় অবশ্যই এক লাইনে লিখে দিতে হবে — "Array indexing starts from 1" — নাহলে examiner 0-based ধরে নিতে পারেন এবং answer ভুল মনে হতে পারে।
2.5 Bubble Up (Heapify-Up) — Term ব্যাখ্যা
Bubble Up মানে হলো নতুন insert করা element-টিকে বার বার তার parent-এর সাথে compare করে, যদি প্রয়োজন হয়, উপরের দিকে সরিয়ে নেওয়া — ঠিক যেন বুদবুদ (bubble) পানির নিচ থেকে উপরে উঠে আসে।
কেন দরকার: নতুন element array-এর শেষে বসানোর পর সেটা হয়তো তার parent-এর চেয়ে বড় হয়ে যেতে পারে (Max Heap property ভেঙে যায়)। এই ভাঙা property ঠিক করার জন্যই element-টাকে ধাপে ধাপে উপরে তুলে সঠিক জায়গায় বসাতে হয়।
3. Exam Definition (English)
Heap: A heap is a complete binary tree that satisfies the heap property — in a Max Heap, every parent node is greater than or equal to its children.
Insertion in Heap: The insertion operation adds a new element at the last position of the array (maintaining the complete binary tree property), and then restores the heap property by repeatedly comparing the new element with its parent and swapping if necessary — this process is called Bubble Up or Heapify-Up, and it runs in O(log n) time.
4. Concept Explanation (বাংলায়)
যখন আমরা একটি নতুন element heap-এ insert করি, তখন আমরা সেটাকে সরাসরি সঠিক জায়গায় বসাতে পারি না, কারণ heap-এর shape (complete binary tree) ঠিক রাখতে হবে। তাই প্রথমে element-টাকে array-এর একদম শেষে বসিয়ে দেওয়া হয় — এতে shape ঠিক থাকে, কিন্তু heap property (parent ≥ child) ভেঙে যেতে পারে।
এরপর আমরা element-টাকে তার parent-এর সাথে তুলনা করি। যদি নতুন element parent-এর চেয়ে বড় হয় (Max Heap-এর ক্ষেত্রে), তাহলে তাদের মধ্যে swap করা হয় — এতে element-টা এক ধাপ উপরে উঠে যায়। এই প্রক্রিয়া তখনই থামে যখন হয় element root-এ পৌঁছে যায়, অথবা তার parent-এর চেয়ে ছোট বা সমান হয়ে যায় (তখন আর property ভাঙা নেই)।
5. Algorithm (English)
INSERT(Heap A, size n, value X)
n = n + 1 // increase heap size by 1
A[n] = X // place new element at the last position
i = n // start from the newly inserted index
while i > 1 do // while not at root
parent = i / 2 // integer division (1-based indexing)
if A[i] > A[parent] then // Max Heap violation check
swap(A[i], A[parent])
i = parent // move pointer up
else
break // heap property restored, stop
end while
6. Step-by-Step Explanation (বাংলায়)
Step 1: নতুন element শেষে বসানো
নতুন element-কে array-এর একদম শেষ index-এ (index = n+1) বসানো হয়। এটাই complete binary tree-এর একমাত্র বৈধ জায়গা যেখানে shape না ভেঙে নতুন node যোগ করা যায়।
কেন দরকার: heap সবসময় complete binary tree হতে হবে; শেষ level-এর বাম দিকের প্রথম খালি জায়গাই একমাত্র বৈধ position।
Step 2: Parent-এর সাথে Compare
নতুন element-এর index থেকে parent index বের করা হয় (i/2), এবং দুইটার মান তুলনা করা হয়।
কেন দরকার: heap property (parent ≥ child) ঠিক আছে কিনা যাচাই করার জন্য এই compare অবশ্যই দরকার।
Step 3: প্রয়োজনে Swap
যদি নতুন element parent-এর চেয়ে বড় হয়, তাহলে দুইটার মধ্যে swap করা হয় — element-টা parent-এর জায়গায় চলে যায়, আর parent নিচে নেমে আসে।
কেন দরকার: Max Heap property রক্ষা করার জন্য বড় element-কে উপরে তুলতেই হবে।
Step 4: উপরে উঠতে থাকা, যতক্ষণ না থামার শর্ত পূরণ হয়
Swap হওয়ার পর element-এর নতুন index ধরে আবার parent বের করে compare করা হয়। এভাবে চলতেই থাকে যতক্ষণ না element root-এ পৌঁছায় অথবা আর swap লাগে না।
কেন দরকার: একবার swap করলেই সব ঠিক হয়ে যায় না — উপরের দিকেও property ভাঙতে পারে, তাই পুরো path ধরে root পর্যন্ত check করতে হয়।
7. ASCII Diagram
Before Insertion
75
/ \
62 50
/ \ / \
47 42 35 29
/
15
After Insertion of 80 (Bubble Up complete)
80
/ \
75 50
/ \ / \
62 42 35 29
/ \
15 47
8. Solve the Question — Step by Step
Given Heap (1-based array): A = [75, 62, 50, 47, 42, 35, 29, 15], size = 8. Insert 80.
Step 1 — Place 80 at the last position
Index
1
2
3
4
5
6
7
8
9
Value
75
62
50
47
42
35
29
15
80
কী করলাম: 80-কে array-এর index 9-এ (শেষে) বসালাম। কেন করলাম: complete binary tree shape ঠিক রাখার জন্য এটাই একমাত্র বৈধ position। এরপর কী হবে: এখন 80-এর parent-এর সাথে compare করতে হবে।
কী করলাম: index 9 আর index 4-এর মান swap করলাম। কেন করলাম: 80 তার parent 47-এর চেয়ে বড়, তাই Max Heap property ভেঙে গিয়েছিল — swap করে সেটা ঠিক করলাম। এরপর কী হবে: 80 এখন index 4-এ আছে, এবার তার নতুন parent-এর সাথে compare করতে হবে।
কী করলাম: index 4 আর index 2-এর মান swap করলাম। কেন করলাম: 80, 62-এর চেয়ে বড় হওয়ায় property আবার ভাঙা ছিল। এরপর কী হবে: 80 এখন index 2-এ, root-এর সাথে compare বাকি।
কী করলাম: index 2 আর index 1 (root) swap করলাম। কেন করলাম: 80, root 75-এর চেয়েও বড়, তাই root পর্যন্ত property ভাঙা ছিল। এরপর কী হবে: 80 এখন root (index 1)-এ, আর উপরে যাওয়ার জায়গা নেই।
Step 5 — Reached Root → STOP
কী করলাম: 80 index 1 অর্থাৎ root-এ পৌঁছে গেছে। কেন থামলাম: root-এর কোনো parent নেই, তাই আর compare করার প্রয়োজন নেই। ফলাফল: সম্পূর্ণ heap-এ এখন আর কোথাও Max Heap property ভাঙা নেই।
9. Final Exam Answer (English)
Final Max Heap after inserting 80:
80, 75, 50, 62, 42, 35, 29, 15, 47
10. Common Mistakes
0-based এবং 1-based indexing গুলিয়ে ফেলা — সবসময় লিখে দাও কোন indexing ব্যবহার করছ।
শুধু একবার swap করেই থেমে যাওয়া — root পর্যন্ত compare চালিয়ে যেতে হবে।
নতুন element মাঝখানে বা root-এ সরাসরি বসিয়ে দেওয়া — সবসময় শেষে বসাতে হবে, এটাই নিয়ম।
Parent-এর বদলে child-এর সাথে compare করা (এটা delete-এর নিয়ম, insert-এর না)।
Array আর Tree — দুটো representation একসাথে না দেখানো (examiner উভয়ই দেখতে চান)।
11. Viva Questions
Q: Heap insert করার সময় নতুন element কোথায় বসানো হয় এবং কেন?
Q: Bubble Up আর Heapify Down-এর মধ্যে পার্থক্য কী?
Q: Insertion-এর time complexity O(log n) কেন?
Q: 1-based আর 0-based indexing-এ parent/child formula কীভাবে আলাদা?
Q: যদি নতুন element তার parent-এর চেয়ে ছোট হয়, তাহলে কী হবে?
Q: Insert করার পর heap শুধু max heap property মেনে চলে, নাকি shape property-ও লাগে?
12. Practice Questions (Exam Style)
Insert element 90 into the max heap: 85, 70, 60, 55, 40, 30, 20 and show all steps.
Insert element 5 into the min heap: 10, 20, 15, 30, 25, 40 and show all steps.
Insert the elements 12, 8, 25, 6, 15 one by one into an initially empty max heap and show the heap after each insertion.
Given the max heap array [90, 80, 70, 60, 50], insert 65 and show the resulting array with all compare/swap steps.
Explain why the new element in heap insertion is always placed at the last index of the array.
Derive the time complexity of the heap insertion operation.
Show both the array representation and the tree diagram before and after inserting 100 into the heap: 95, 88, 77, 60, 55, 40, 30.
State the parent, left child, and right child index formulas for both 1-based and 0-based indexing.