হিপ ও প্রায়োরিটি কিউপড়তে ৫ মিনিট লাগবে

হিপ সর্ট (Heap Sort)

অতিরিক্ত মেমোরি ছাড়াই O(n log n) স্পিডে সর্ট করার গ্যারান্টি

build heap: O(n)sort: O(n log n)space: O(1) (ইন-প্লেস)

হিপ সর্ট (Heap sort) মেইনলি হিপের দুটো বেসিক কাজকে খুব সুন্দর করে মিলিয়ে একটা সর্টিং বা সাজানেনর অ্যালগরিদম তৈরি করে। এটা মার্জ সর্টের (merge sort) মতো সবসময় O(n log n) স্পিডের গ্যারান্টি দেয়, আবার কুইক সর্টের (quicksort) মতো অতিরিক্ত কোনো মেমোরি বা লেজ (O(1) extra space) ছাড়া অরিজিনাল অ্যারের ভেতরেই কাজ সেরে ফেলে — তবে এর একটা ছোট সমস্যান আছে, যেটা পরে বলছি।

এর পুরো কাজটা দুটো ধাপে হয়:

একটা ম্যাক্স-হিপ (max-heap) বানানো: ফ্লয়েডের 'হিপিফাই (heapify)' অ্যালগরিদম দিয়ে অগোছালো অ্যারেটাকে একটা ম্যাক্স-হিপে রূপান্তর করা হয় — যাতে সময় লাগে O(n)।
এক এক করে তুলে আনা (Extract repeatedly): হিপের মাথা বা রুট (root) হলো সবচেয়ে বড় সংখ্যা। এটাকে অ্যারের একদম শেষের সংখ্যার সাথে জায়গা বদল (swap) করে অ্যারের শেষে ফিক্সড করে দেওয়া হয়। এরপর হিপের সাইজ বা সীমানা ১ কমিয়ে দেওয়া হয় এবং রুটটাকে আবার জায়গা মতো বসাতে 'সিফট ডাউন (sift down)' করা হয়। এই কাজটা n-1 বার করা হয় — যাতে সময় লাগে O(n log n)।

প্রতিবার যখন রুটটাকে শেষে পাঠানো হয়, তখন ডান দিক থেকে একটা একটা করে বড় সংখ্যা জমা হতে থাকে এবং একটা সর্টেড বা সাজানেন লাইন তৈরি হয়। এর জন্য কোনো নতুন অ্যারে লাগে না — শুধু অরিজিনাল অ্যারের ভেতরেই একটা কাল্পনিক "হিপের সীমানা" ক্রমশ ছোট হতে থাকে।

◈ Watch heap sort

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

[4, 1, 3, 2, 6]-এর ওপর ধাপে ধাপে কাজ

pseudocode

ইনপুট:      [4, 1, 3, 2, 6]
ম্যাক্স-হিপ: [6, 4, 3, 2, 1]   (heapify বা হিপ বানানোর পর)

6 বের করুন: অদলবদল (swap) → [1, 4, 3, 2, | 6], সিফট ডাউন → [4, 2, 3, 1, | 6]
4 বের করুন: অদলবদল (swap) → [1, 2, 3, | 4, 6], সিফট ডাউন → [3, 2, 1, | 4, 6]
3 বের করুন: অদলবদল (swap) → [1, 2, | 3, 4, 6], সিফট ডাউন → [2, 1, | 3, 4, 6]
2 বের করুন: অদলবদল (swap) → [1, | 2, 3, 4, 6]
রেজাল্ট:   [1, 2, 3, 4, 6]

এত ভালো হওয়া সত্ত্বেও হিপ সর্ট কেন সবাই ব্যবহার করে না?

অঙ্কের হিসাবে বা 'বিগ-ও (Big-O)'-তে একবারে পারফেক্ট হওয়া সত্ত্বেও, দুনিয়াতে কুইক সর্ট বা মার্জ সর্টের তুলনায় হিপ সর্টের ব্যবহার খুবই কম। এর মূল কারণ হলো ক্যাশে মেমোরির পারফরম্যান্স (Cache performance)।

কুইক সর্ট যখন কাজ করে, সে মেমোরির পরপর থাকা ডেটাগুলোকে পড়ে (sequential access)। কিন্তু হিপ সর্টের সিফট ডাউন (sift-down) বারবার বাপ-বেটার (parent-child) পজিশন মানে i, 2i+1, 2i+2 — এর মধ্যে লাফাতে থাকে। অনেক বড় অ্যারের ক্ষেত্রে এই লাফালাফির কারণে সিপিইউ ক্যাশে মিস (CPU cache miss) হয়। ফলে স্পিডের হিসাব এক হলেও, বাস্তবে বা প্র্যাকটিক্যালি হিপ সর্ট ২ থেকে ৫ গুণ পর্যন্ত স্লো বা ধীরগতির হয়ে যায়।

হিপ সর্ট বনাম মার্জ সর্ট বনাম কুইক সর্ট

হিপ সর্ট: সবসময় O(n log n), জায়গা নেয় O(1), ক্যাশে ফ্রেন্ডলি নয়, স্টেবল (stable) নয়।
মার্জ সর্ট: সবসময় O(n log n), জায়গা নেয় O(n), ক্যাশে ফ্রেন্ডলি (পরপর পড়ে), স্টেবল।
কুইক সর্ট: গড়ে O(n log n) কিন্তু সবচেয়ে খারাপ অবস্থায় O(n²), জায়গা নেয় O(log n), চরম ক্যাশে ফ্রেন্ডলি, স্টেবল নয়।

দ্রষ্টব্য: ইন্টারভিউতে যদি কেউ এমন কোনো সর্টিং অ্যালগরিদম চায় যেটা গ্যারান্টি দিয়ে O(n log n) স্পিড দেবে আবার কোনো বাড়তি মেমোরিও (in-place) খাবে না — তখন একটাই উত্তর: হিপ সর্ট। ইন্টারভিউয়ারকে যদি বলেন, 'আমি স্টেবিলিটি চাইলে মার্জ সর্ট নিতাম, কিন্তু মেমোরি বাঁচানোর কড়া শর্ত থাকলে হিপ সর্ট নেবো' — তাহলে সে বুঝবে আপনি শুধু মুখস্থ করেননি, এদের আসল পার্থক্যটাও বোঝেন।