সর্টিং৭ মিনিট পড়া

হিপ সর্ট (Heap Sort)

এমন একটি টুর্নামেন্ট ব্র্যাকেট যেখানে চ্যাম্পিয়ন সবসময় সবার ওপরে উঠে আসে
time (all cases):O(n log n)space:O(1) (ইন-প্লেস)stable:নাbuild heap:O(n)

একটি টুর্নামেন্ট ব্র্যাকেটের কথা ভাবুন যেখানে প্রতিটি ম্যাচ প্রতিটি রাউন্ডে একই সাথে খেলা হয়। নিয়ম হলো: প্রতিটি ম্যাচের বিজয়ীকে অবশ্যই তার দুটি সন্তানের চেয়ে শক্তিশালী হতে হবে। যেকোনো রাউন্ডের শেষে, ব্র্যাকেটের একদম শীর্ষে সবচেয়ে শক্তিশালী খেলোয়াড় অবস্থান করে। তাকে বের করে নিন, ব্র্যাকেটটি সংকুচিত করুন এবং আবার খেলা শুরু করুন — এবার পরবর্তী সবচেয়ে শক্তিশালী খেলোয়াড়টি ওপরে উঠে আসবে। এটিই হলো হিপ সর্ট।

আরও নিখুঁতভাবে বললে: এটি একটি ম্যাক্স-হিপ (max-heap) ব্যবহার করে — এটি এমন একটি বাইনারি ট্রি যেখানে প্রতিটি অভিভাবক (parent) তার সন্তানদের (children) চেয়ে বড় হয়। অ্যারের মাধ্যমে এটিকে খুব সংক্ষেপে সংরক্ষণ করা যায়: i ইনডেক্সের সন্তানরা 2i+1 এবং 2i+2 এ থাকে; i এর অভিভাবক ⌊(i−1)/2⌋ এ থাকে। এর জন্য কোনো পয়েন্টারের প্রয়োজন হয় না।

ধাপ ১: O(n) সময়ে হিপ তৈরি করা

আপনি হয়তো ভাবতে পারেন যে একটি হিপের মধ্যে n সংখ্যক উপাদান একে একে ঢোকাতে (insert) O(n log n) সময় লাগে। তবে এর একটি আরও বুদ্ধিদীপ্ত উপায় আছে: ফ্লয়েডের হিপিফাই (Floyd's heapify)। একদম শেষের নন-লিফ নোড (ইনডেক্স ⌊n/2⌋−1) থেকে শুরু করুন এবং উল্টো দিকে কাজ করুন, প্রতিটি নোডকে তার সঠিক অবস্থানে নামিয়ে দিন (sift down)। লিফ নোডগুলোর (leaves) কোনো কাজ করতে হয় না; নিচের দিকের নোডগুলোর খুব সামান্য কাজ করতে হয়। সবগুলো কাজের যোগফল একটি জ্যামিতিক ধারায় (geometric series) পরিণত হয় যা O(n) এ গিয়ে মেশে — এটি একটি চমকপ্রদ তথ্য যা সমস্ত উচ্চতা h এর সাপেক্ষে h·n/2^h এর যোগফল বের করে প্রমাণ করা যায়।

ধাপ ২: বারবার এক্সট্র্যাক্ট-ম্যাক্স (Extract-Max) করে সর্ট করা

এখন সবচেয়ে বড় উপাদানটি রুটে (ইনডেক্স 0) রয়েছে। এটিকে হিপের সর্বশেষ উপাদানের সাথে অদলবদল (swap) করুন, হিপটিকে এক ঘর ছোট করুন এবং হিপের প্রপার্টি বা নিয়ম ধরে রাখতে নতুন রুটটিকে নিচের দিকে নামিয়ে দিন। বের করে আনা উপাদানটি এখন অ্যারের শেষে সঠিক সারিবদ্ধ (sorted) অবস্থানে চলে গেছে। এই প্রক্রিয়াটি n−1 বার পুনরাবৃত্তি করুন। প্রতিটি নামিয়ে দেওয়ার বা সিফট-ডাউন কাজে O(log n) সময় লাগে, এবং আমরা এমন কাজ n বার করি: মোট O(n log n) কাজ।

এই সর্টিং পুরোপুরি ইন-প্লেস (in-place) কাজ করে। হিপটি অ্যারের সামনের দিকে থাকে; আর সাজানো বা সর্ট করা অংশটি পেছন থেকে বাড়তে থাকে। এর জন্য কোনো অতিরিক্ত বাফারের প্রয়োজন পড়ে না।

কেন হিপ সর্ট বাস্তবে হেরে যায়

এর চমৎকার বৈশিষ্ট্যগুলো থাকা সত্ত্বেও — যেমন O(n log n) গ্যারান্টিযুক্ত সময়, O(1) স্পেস, কোনো প্রতিকূল ইনপুট নেই — হিপ সর্ট বাস্তবে কুইক সর্টের চেয়ে ধীরগতি সম্পন্ন। এর মূল কারণ হলো: ক্যাশ মেমরির সাথে অসহযোগিতা (cache unfriendliness)। সিফট-ডাউন প্রক্রিয়াটি অভিভাবক (ইনডেক্স i) এবং সন্তানের (ইনডেক্স 2i+1) মধ্যে লাফিয়ে লাফিয়ে কাজ করে, যা বড় অ্যারের ক্ষেত্রে একে অপরের থেকে অনেক দূরে থাকে। এই ধরনের চলাচলের কারণে বারবার সিপিইউ ক্যাশ মিস (CPU cache misses) হয়, যার ফলস্বরূপ হিপ সর্ট বাস্তব ক্ষেত্রে কুইক সর্টের চেয়ে ২-৫ গুণ ধীর হয়ে যায়।

মার্জ সর্ট ক্রমিক বা ক্রমানুসারে মেমরি অ্যাক্সেস করে (ক্যাশ-বান্ধব)। কুইক সর্ট কাছাকাছি থাকা অংশ বা কন্টিগুয়াস রেঞ্জকে ভাগ করে (ক্যাশ-বান্ধব)। কিন্তু হিপ সর্ট এদিক-ওদিক লাফিয়ে বেড়ায় — যা ক্যাশ-বান্ধব নয়। এর সবচেয়ে বড় উপযোগিতা হলো এটি ইন্ট্রোসর্ট (Introsort) এ একটি সেফটি নেট (safety net) হিসেবে কাজ করে: যখন কুইক সর্ট বুঝতে পারে যে তার পারফরম্যান্স নিচে নেমে যাচ্ছে (রিকার্শন গভীরতা > 2 log n), তখন এটি কোনো অতিরিক্ত মেমরি ছাড়াই O(n log n) গ্যারান্টির জন্য হিপ সর্টের আশ্রয় নেয়।

দ্রষ্টব্য: ফ্লয়েডের হিপিফাই (Floyd's heapify) হলো একটু চালাকি করা O(n) ট্রিক: এটি ট্রির নিচ থেকে কাজ শুরু করে, যেখানে বেশিরভাগ নোড থাকে এবং প্রায় কোনো কাজই করতে হয় না। কেবল শীর্ষের দিকের নোডগুলোই (যাদের সংখ্যা খুব কম) আসল কাজ করে। এর পেছনের অঙ্কটি হলো: Σ h·(n/2^h) = O(n)। একটি হিপ তৈরি করা একটি লিনিয়ার কাজ!

হিপ সর্ট ইমপ্লিমেন্টেশন

def heapify(arr, n, i):
    """Sift arr[i] down within heap of size n."""
    largest = i
    left, right = 2*i + 1, 2*i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)
    # Phase 1: Build max-heap in O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Phase 2: Extract max n-1 times
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # move max to sorted section
        heapify(arr, end, 0)                   # restore heap in remaining part
    return arr


data = [12, 11, 13, 5, 6, 7]
print(heap_sort(data))
Output
[5, 6, 7, 11, 12, 13]

Complexity

🏗️ ম্যাক্স-হিপ তৈরি (Floyd's)
নিচ থেকে উপরের দিকে (bottom-up) হিপিফাই করা হয়; জ্যামিতিক ধারার যোগফল দাঁড়ায় O(n)
লিনিয়ার — আশ্চর্যজনকভাবে দ্রুত O(n)
📤 এক্সট্র্যাক্ট-ম্যাক্স (নিচে নামানো বা sift down)
রুটকে (root) অ্যারের শেষে পাঠানো হয়, তারপর হিপের নিয়ম পুনরুদ্ধার করতে নতুন রুটকে নিচে নামানো হয়
প্রতিটি এক্সট্র্যাক্টে লগারিদমিক O(log n)
⏱️ সার্বিক সর্ট — সব ক্ষেত্রে
O(n) তৈরি করা + O(n log n) সংখ্যক এক্সট্র্যাক্ট করা — সবচেয়ে ভালো = সবচেয়ে খারাপ = গড়
লিনিয়ারদমিক, কোনো খারাপ ইনপুট নেই O(n log n)
💾 অক্সিলিয়ারি স্পেস (Auxiliary space)
সাজানো অংশটি একই অ্যারেতে বাড়তে থাকে — অতিরিক্ত কোনো বাফারের প্রয়োজন নেই
ধ্রুবক (Constant) — সত্যিই ইন-প্লেস O(1)

ছোট কুইজ

ফ্লয়েডের অ্যালগরিদম ব্যবহার করে একটি ম্যাক্স-হিপ তৈরি করতে কত সময় (time complexity) লাগে?

পড়া চালিয়ে যান