Topic 12 · Heap
Build Heap ও Heap Sort
একটা এলোমেলো array কে heap বানানো, তারপর সেই heap দিয়ে sort করা। মজার ব্যাপার —
নতুন কিছু শিখতে হবে না, Heapify Down টাই বারবার ব্যবহার হবে।
১. প্রশ্ন (Question)
EXAM QUESTION
(a) নিচের array কে Max Heap এ রূপান্তর করো (build heap), প্রতিটি ধাপ দেখাও:
4, 10, 3, 5, 1
(b) তৈরি হওয়া heap ব্যবহার করে Heap Sort করো এবং প্রতিটি ধাপে array লেখো।
(c) Build Heap এর complexity O(n) আর Heap Sort এর
O(n log n) — ব্যাখ্যা করো।
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ Heapify Down — এটাই একমাত্র হাতিয়ার
একটা node কে তার দুই child এর মধ্যে
বড়টার সাথে তুলনা করে, দরকার হলে swap করে
নিচে নামিয়ে আনার প্রক্রিয়া (
Topic 11 এ বিস্তারিত)।
কেন দরকার: Build Heap আর Heap Sort — দুইটাই আসলে heapify down এর বারবার প্রয়োগ।
নতুন কোনো নিয়ম নেই।
২.২ Leaf গুলো এমনিতেই heap
Array এর দ্বিতীয়ার্ধ — অর্থাৎ index n/2 + 1 থেকে n পর্যন্ত সব
element ই leaf।
কেন: index i এর left child হয় 2i। i যদি n/2 এর চেয়ে বড় হয়, তাহলে 2i > n —
অর্থাৎ ওই index এর কোনো child ই array এর ভেতরে নেই।
কেন দরকার: Leaf এর নিচে কেউ নেই, তাই সে নিজেই একটা বৈধ heap। তার উপর কাজ করার
দরকারই নেই। এজন্যই build heap শুরু হয় index n/2 থেকে, n থেকে নয় — এতে অর্ধেক
কাজ বেঁচে যায়।
২.৩ নিচ থেকে উপরে কাজ করতে হবে
Build heap এ index n/2 থেকে শুরু করে 1 পর্যন্ত উল্টো দিকে
(n/2, n/2−1, …, 2, 1) heapify down চালাতে হয়।
কেন উল্টো দিকে: কোনো node কে heapify down করার সময় ধরে নেওয়া হয় তার নিচের
দুইটা subtree ইতিমধ্যেই বৈধ heap। নিচ থেকে শুরু করলে এই শর্তটা সবসময় সত্য থাকে।
উপর থেকে শুরু করলে শর্তটা ভেঙে যায় এবং heap ভুল তৈরি হয়।
২.৪ Heap Sort এর মূল বুদ্ধি
Max heap এ সবচেয়ে বড় value সবসময় root এ (index 1) থাকে। আর sorted array তে সবচেয়ে
বড় value থাকা উচিত সবার শেষে।
তাই: root আর শেষ element কে swap করে দাও — বড়টা তার সঠিক জায়গায় চলে গেল।
তারপর heap size এক কমিয়ে বাকি অংশ আবার heapify করো। এভাবে n−1 বার করলেই পুরো array sorted।
কেন আলাদা array লাগে না: swap করে শেষে রেখে দিচ্ছি বলে একই array এর ডান দিকটা
ধীরে ধীরে sorted হয়ে যাচ্ছে — এজন্যই heap sort in-place, বাড়তি মেমরি লাগে না।
৩. Exam Definition (English)
Build Heap (Heapify): Building a heap converts an arbitrary array into a valid heap by
applying the heapify-down operation to every internal node, starting from the last internal node
at index ⌊n/2⌋ and moving upward to the root at index 1. Elements from index
⌊n/2⌋ + 1 to n are leaves and already satisfy the heap property, so they
are skipped. The total cost is O(n), not O(n log n), because most nodes
lie near the bottom of the tree and therefore sink only a short distance.
Heap Sort: Heap sort first builds a max heap from the input array. It then repeatedly
swaps the root (the maximum element) with the last element of the heap, reduces the heap size by
one, and restores the heap property by heapifying down from the root. After n − 1
iterations the array is sorted in ascending order.
Complexity: Build heap O(n) + n − 1 heapify-down operations of
O(log n) each = O(n log n) in all cases (best, average and worst).
Heap sort is in-place (O(1) extra space) but not stable.
৪. Concept Explanation (বাংলায়)
Build Heap: ভাবো একটা ক্লাসে সবাই এলোমেলোভাবে দাঁড়িয়ে আছে, কিন্তু নিয়ম হলো প্রতিটা
দলের নেতা তার দলের সবার চেয়ে লম্বা হতে হবে। সবচেয়ে ছোট দলগুলো (একজনের দল = leaf)
এমনিতেই নিয়ম মানে। তাই আমরা শুরু করি সবচেয়ে নিচের ছোট দল থেকে, ঠিক করি, তারপর
এক ধাপ উপরের দলে যাই। উপরের দলে যাওয়ার সময় জানি — নিচের সব দল ঠিক হয়ে আছে,
তাই শুধু নেতাকে সঠিক জায়গায় নামিয়ে দিলেই পুরো দল ঠিক।
Heap Sort: Heap বানানোর পর সবচেয়ে বড় লোকটা একদম উপরে দাঁড়িয়ে আছে। তাকে
লাইনের একদম শেষে পাঠিয়ে দাও (swap), আর বলে দাও "তুমি আর খেলায় নেই" (size কমাও)।
এখন উপরে যে নতুন লোক এলো সে হয়তো যোগ্য নয় — তাকে নামিয়ে দাও (heapify down)।
আবার নতুন সবচেয়ে বড় লোক উপরে উঠবে, তাকেও শেষে পাঠাও। এভাবে প্রতিবার একজন করে
তার সঠিক জায়গায় বসে যাবে — শেষে পুরো লাইন ছোট থেকে বড় ক্রমে সাজানো।
৫. Algorithm (English)
BUILD_MAX_HEAP(A, n) // A is 1-based
for i = n / 2 down to 1 do // skip the leaves
HEAPIFY_DOWN(A, n, i)
HEAP_SORT(A, n)
BUILD_MAX_HEAP(A, n)
for size = n down to 2 do
swap A[1] and A[size] // biggest goes to its final place
HEAPIFY_DOWN(A, size - 1, 1) // fix the shrunken heap
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
swap A[i] and A[largest]
i = largest
৬. ধাপে ধাপে ব্যাখ্যা (বাংলায়)
ধাপ ১ — শেষ internal node খুঁজে বের করো
i = n / 2 (ভাগশেষ বাদ)। n = 5 হলে i = 2।
কেন এখান থেকে: index 3, 4, 5 সবই leaf (2×3 = 6 > 5)।
Leaf এর নিচে কেউ নেই, তাই তারা এমনিতেই heap — সময় নষ্ট করার দরকার নেই।
ধাপ ২ — i থেকে 1 পর্যন্ত উল্টো দিকে heapify down চালাও
i = n/2, n/2 − 1, …, 2, 1 — এই ক্রমে।
কেন উল্টো ক্রম: heapify down ঠিকভাবে কাজ করে শুধু তখনই
যখন নিচের দুই subtree আগে থেকেই বৈধ heap। নিচ থেকে উপরে গেলে এই শর্ত সবসময় মেনে চলা হয়।
ধাপ ৩ — Heap Sort: root আর শেষ element swap করো
A[1] ↔ A[size]। এখন সবচেয়ে বড় value তার চূড়ান্ত জায়গায়।
কেন এটাই চূড়ান্ত জায়গা: max heap এ root ই সবচেয়ে বড়, আর ascending
sorted array তে সবচেয়ে বড়টা সবার শেষে বসে। তাই আর কখনো তাকে নাড়াতে হবে না।
ধাপ ৪ — Heap size এক কমিয়ে root থেকে heapify down করো
Swap করে আনা নতুন root সাধারণত ছোট, তাই তাকে নামাতে হবে।
কেন শুধু root থেকে: কারণ শুধু root এর জায়গাটাই বদলেছে, বাকি
পুরো গাছ আগের মতোই বৈধ heap আছে। তাই পুরো build heap আবার চালানোর দরকার নেই।
ধাপ ৫ — size = 1 হওয়া পর্যন্ত চালাও
একটা element বাকি থাকলে সেটা নিজে থেকেই sorted, তাই n − 1 বার করলেই যথেষ্ট।
কেন n−1 বার: প্রতিবার একটা করে element চূড়ান্ত জায়গায় বসছে।
n−1 টা বসে গেলে শেষেরটা আপনা-আপনি ঠিক জায়গায়।
৭. Q1 সমাধান — Build Heap ট্রেস
শুরুর array (এলোমেলো) :
Index : 1 2 3 4 5
Array : 4 10 3 5 1
4 (1)
/ \
10 (2) 3 (3)
/ \
5 (4) 1 (5)
n = 5 ⇒ শেষ internal node = n/2 = 2
index 3, 4, 5 → leaf, বাদ
খেয়াল করো: Pass 2 এ একটা swap করেই থেমে যাওয়া যায়নি। 4 কে index 1 থেকে
index 2 এ নামানোর পর আবার দেখতে হয়েছে — সেখানেও সে ছোট ছিল, তাই আরও এক ধাপ নেমেছে।
Heapify down মানে একটা swap নয়, নিচে নামতে থাকা। এটাই সবচেয়ে বেশি ভুল হয়।
তৈরি হওয়া Max Heap :
Index : 1 2 3 4 5
Array : 10 5 3 4 1
10 (1)
/ \
5 (2) 3 (3)
/ \
4 (4) 1 (5)
যাচাই: 10 ≥ 5, 3 ✓ · 5 ≥ 4, 1 ✓ — বৈধ Max Heap।
বিকল্প পদ্ধতি — একে একে Insert করা: খালি heap এ 4, 10, 3, 5, 1 একে একে insert করেও
heap বানানো যায় (
Topic 10 এর bubble up দিয়ে)। কিন্তু —
• Build Heap পদ্ধতি:
O(n)
• একে একে insert:
O(n log n)
তাছাড়া দুই পদ্ধতিতে
ভিন্ন heap ও আসতে পারে — দুইটাই বৈধ, কারণ একই সংখ্যার একাধিক
বৈধ heap থাকতে পারে। প্রশ্নে "build heap" বললে
n/2 পদ্ধতিই ব্যবহার করো।
৮. Q2 সমাধান — Heap Sort ট্রেস
শুরু : 10 5 3 4 1 (heap size = 5)
└──────── heap ────────┘
Pass 1 — size 5
A[1] ↔ A[5] : 10 আর 1 swap →
1 5 3 4 | 10, heap size = 4
Heapify(1): child A[2]=5, A[3]=3 → বড় 5; 1 < 5 swap →
5 1 3 4 | 10
i=2: child A[4]=4 (A[5] heap এর বাইরে) → বড় 4; 1 < 4 swap →
5 4 3 1 | 10
i=4: child নেই → থামো
Array : 5 4 3 1 | 10
└──── heap ────┘ sorted
Pass 2 — size 4
A[1] ↔ A[4] : 5 আর 1 swap →
1 4 3 | 5 10, heap size = 3
Heapify(1): child A[2]=4, A[3]=3 → বড় 4; 1 < 4 swap →
4 1 3 | 5 10
i=2: A[4] heap এর বাইরে → থামো
Array : 4 1 3 | 5 10
└── heap ──┘ sorted
Pass 3 — size 3
A[1] ↔ A[3] : 4 আর 3 swap →
3 1 | 4 5 10, heap size = 2
Heapify(1): child A[2]=1; 3 > 1 → swap লাগবে না, থামো
Array : 3 1 | 4 5 10
└heap┘ sorted
Pass 4 — size 2
A[1] ↔ A[2] : 3 আর 1 swap →
1 | 3 4 5 10, heap size = 1
একটা element বাকি → কাজ শেষ
Array : 1 | 3 4 5 10
└───── sorted ────┘
Sorted array = 1, 3, 4, 5, 10
Max Heap দিয়ে sort করলে ফলাফল ascending (ছোট → বড়)
Descending চাইলে Min Heap ব্যবহার করতে হবে
(c) Complexity ব্যাখ্যা
Build Heap কেন O(n), O(n log n) নয়:
গাছের বেশিরভাগ node
একদম নিচে থাকে। n টা node এর মধ্যে প্রায় অর্ধেকই leaf —
তাদের কোনো কাজই নেই। তার উপরের level এ n/4 টা node, তারা সর্বোচ্চ 1 ধাপ নামে।
তার উপরে n/8 টা, তারা 2 ধাপ। এভাবে যোগ করলে —
মোট কাজ ≈ n/4 × 1 + n/8 × 2 + n/16 × 3 + … ≈ n
অর্থাৎ শুধু root এর মতো হাতেগোনা কয়েকটা node ই পুরো log n পথ নামে। তাই মোট
O(n)।
Heap Sort কেন O(n log n): Build heap লাগে O(n), তারপর n−1 বার heapify down,
প্রতিবার সর্বোচ্চ log n ধাপ → O(n log n)। যোগ করলে
O(n) + O(n log n) = O(n log n)।
বিশেষ কথা: Heap sort এর best, average, worst —
তিনটাই O(n log n)।
Quick sort এর worst case O(n²), কিন্তু heap sort এর কখনো হয় না। তবে heap sort
stable নয় (সমান value গুলোর আপেক্ষিক ক্রম বদলে যেতে পারে) এবং
in-place (বাড়তি মেমরি O(1))।
৯. Final Exam Answer (English)
Build heap + heap sort trace
Input : 4 10 3 5 1 (n = 5, start at i = 2)
Build heap
i = 2 : 4 10 3 5 1 no swap (10 > 5, 1)
i = 1 : 10 4 3 5 1 swap 4 <-> 10
: 10 5 3 4 1 swap 4 <-> 5 ← max heap
Heap sort
pass 1 : 5 4 3 1 | 10
pass 2 : 4 1 3 | 5 10
pass 3 : 3 1 | 4 5 10
pass 4 : 1 | 3 4 5 10
Sorted : 1 3 4 5 10
Build heap O(n) · Heap sort O(n log n) in best, average and worst case
In-place (O(1) extra space) · Not stable
১০. Common Mistakes
- Index n থেকে শুরু করা — শুরু হবে
n/2 থেকে। Leaf গুলোতে heapify চালানো অপ্রয়োজনীয়।
- উপর থেকে নিচে (1 → n/2) heapify করা — ভুল heap তৈরি হবে। নিচ থেকে উপরে যেতে হবে।
- Heapify down এ একটা swap করেই থেমে যাওয়া — element কে যতদূর নামা দরকার ততদূর নামাতে হবে; প্রতি level এ আবার তুলনা।
- Heap sort এ প্রতিবার পুরো build heap আবার চালানো — শুধু root থেকে একবার heapify down যথেষ্ট, কারণ বাকি গাছ ঠিকই আছে।
- Heap size কমাতে ভুলে যাওয়া — swap করে শেষে পাঠানো element আর heap এর অংশ নয়। না কমালে সে আবার heap এ ফিরে আসবে।
- Max heap দিয়ে descending আশা করা — Max heap দিয়ে sort করলে ascending আসে। Descending চাইলে min heap।
- Build Heap এর complexity O(n log n) লেখা — উত্তর O(n), আর কেন সেটাও ব্যাখ্যা করতে হবে।
- প্রতিটা pass এর array না লেখা — ধাপগুলোই নম্বরের জায়গা, শুধু শেষ উত্তর নয়।
১১. Viva Questions
Q: Build heap এ index n/2 থেকে শুরু করা হয় কেন?
Q: নিচ থেকে উপরে heapify করতে হয় কেন? উপর থেকে নিচে করলে কী হবে?
Q: Build heap এর complexity O(n) হয় কীভাবে, যদিও প্রতিটা heapify O(log n)?
Q: Heap sort এর তিনটা case (best/average/worst) এ complexity কত?
Q: Heap sort কি stable? কি in-place? ব্যাখ্যা করো।
Q: Max heap দিয়ে sort করলে ascending না descending আসে এবং কেন?
Q: Heap sort আর Quick sort এর তুলনা করো।
Q: Priority queue implement করতে heap ব্যবহার করা হয় কেন?
১২. Practice Questions
3, 9, 2, 1, 4, 5 কে Max Heap এ রূপান্তর করো।
উত্তর দেখাও
n = 6, শুরু i = 3।
i=3: A[3]=2, child A[6]=5 → swap → 3 9 5 1 4 2
i=2: A[2]=9, child 1, 4 → 9 বড়, swap নেই
i=1: A[1]=3, child 9, 5 → বড় 9, swap → 9 3 5 1 4 2; এখন i=2: child 1, 4 → বড় 4, swap → 9 4 5 1 3 2
উত্তর: 9 4 5 1 3 2 (যাচাই: 9≥4,5 ✓ · 4≥1,3 ✓ · 5≥2 ✓)
10, 5, 20, 3, 8 কে Min Heap এ রূপান্তর করো।
উত্তর দেখাও
n = 5, শুরু i = 2।
i=2: A[2]=5, child A[4]=3, A[5]=8 → ছোট 3; 5 > 3 swap → 10 3 20 5 8
i=1: A[1]=10, child 3, 20 → ছোট 3, swap → 3 10 20 5 8; i=2: child 5, 8 → ছোট 5, swap → 3 5 20 10 8
উত্তর: 3 5 20 10 8
- Max Heap
9 4 5 1 3 2 ব্যবহার করে সম্পূর্ণ Heap Sort করো।
উত্তর দেখাও
Pass 1: swap 9↔2 → 2 4 5 1 3 |9; heapify → 5 4 2 1 3 |9
Pass 2: swap 5↔3 → 3 4 2 1 |5 9; heapify → 4 3 2 1 |5 9
Pass 3: swap 4↔1 → 1 3 2 |4 5 9; heapify → 3 1 2 |4 5 9
Pass 4: swap 3↔2 → 2 1 |3 4 5 9; heapify → 2 1 (ঠিকই আছে)
Pass 5: swap 2↔1 → 1 |2 3 4 5 9
Sorted: 1, 2, 3, 4, 5, 9
- ইতিমধ্যে sorted একটা array
1, 2, 3, 4, 5 কে max heap বানাতে কয়টা swap লাগবে?
উত্তর দেখাও
i=2: A[2]=2, child A[4]=4, A[5]=5 → বড় 5, swap → 1 5 3 4 2 (1টা)
i=1: A[1]=1, child 5, 3 → বড় 5, swap → 5 1 3 4 2 (2টা); i=2: child 4, 2 → বড় 4, swap → 5 4 3 1 2 (3টা)
মোট 3 টা swap, ফলাফল 5 4 3 1 2
- একটা array ইতিমধ্যে max heap হলে build heap এ কয়টা swap লাগবে?
উত্তর দেখাও
শূন্যটা — প্রতিটা তুলনায় parent ইতিমধ্যেই বড়, তাই কোনো swap হয় না। তবে তুলনাগুলো ঠিকই হয়, তাই সময় লাগে O(n)।
- n = 100 হলে build heap এ কত নম্বর index থেকে শুরু করবে এবং কতগুলো node skip হবে?
উত্তর দেখাও
শুরু index 50 থেকে। Index 51–100, অর্থাৎ 50 টা leaf skip হবে।
- Heap Sort আর Merge Sort এর তুলনা করো — সময়, মেমরি, stability এর দিক থেকে।
উত্তর দেখাও
দুইটাই O(n log n)। Merge sort stable কিন্তু O(n) বাড়তি মেমরি লাগে;
Heap sort in-place (O(1)) কিন্তু stable নয়।
- BUILD_MAX_HEAP এর pseudocode লেখো এবং n = 7 এর জন্য কোন index গুলোতে heapify চলবে দেখাও।