হিপ সর্ট

Heap Sort এমন একটি Sorting Algorithm যে Algorithm এ Heap নামের একটি ডাটা স্ট্রাকচার ব্যবহার করা হয় । মার্জ সর্ট এর মত এটিও খুবই কার্যকর একটি Algorithm । তবে মার্জ সর্টের সাথে এর পার্থক্য হল Heap Sort , In Place Algorithm এর আওতাভুক্ত যা মার্জ সর্ট নয় । In Place Algorithm হল আমি ইনপুটকে Process করার  জন্য অতিরিক্ত জায়গা ছাড়াই ইনপুটকে নিয়ে কাজ করতে   পারি । মার্জ সর্টের ক্ষেত্রে আমরা অতিরিক্ত দুটি Array ব্যবহার করে ইনপুটগুলোকে নিয়ে কাজ করেছিলাম ।

   এই Sort এ প্রথমেই আমাদেরকে যা করতে হবে তা হল Heap Property আছে এরকম একটি বাইনারি ট্রি বানাতে হবে । বাইনারি ট্রি হল এমন একটি ট্রি যেখানে প্রতিটি নোডের 0 থেকে সর্বোচ্চ 2 টি Child থাকে । বামের Child কে Left Child এবং ডানের Child কে Right Child বলা হয় ।

আবার , Heap Property দুই রকমের ঃ

• Max Heap ( যেখানে Parent কে তার Child এর সমান বা তার থেকে বড় হতে হবে )
• Min Heap ( যেখানে Parent কে তার Child এর সমান বা তার থেকে ছোট হতে হবে )

এখন ধরা যাক , আমাদের কাছে একটি অ্যারে আছে ঃ

Index(i)	1	2	3	4	5	6	7	8
Value	6	5	3	1	8	7	2	4

এই অ্যারেকে Heap Property ব্যবহার করে সর্ট করতে হবে।

অ্যারে থেকে বাইনারি ট্রি বানানোর নিয়ম হল Parent Node যদি i হয় তাহলে তার

• Left Child হবে (2*i)
• Right Child হবে (2*i+1) 

সাথে সাথে আমরা Check করবো যে আমাদের Heap Property ঠিক আছে কিনা । এখানে আমরা  Max Heap Property ব্যবহার করে ট্রিতে Heap তৈরি করেছি ।

প্রথমে আমরা অ্যারে থেকে একটি একটি করে Index নিবো এবং বাইনারি ট্রি তৈরি করবো । তার সাথে দেখবো ট্রি তে যে নোড যোগ হচ্ছে সেটি থেকে তার Parent Node ছোট কিনা । যদি ছোট হয় তাহলে তার সাথে Child Node টির Value , Swap করবো । অর্থাৎ আমরা ট্রিতে একটি Value যোগ করার সাথে সাথে Heap Property ঠিক আছে কিনা তা Check করে দেখবো । এই কাজটি করা হয়েছে Code এর MakeHeap( ) নামক Function এ । 

এই Function থেকে আমরা প্রথমেই যে ট্রি টি পাবো সেটি দেখতে এরকম ঃ

এখানে যে Root নোড আছে সেটিই সবচেয়ে বড় Value কারণ আমরা ট্রি টি Heap Property maintain করেই তৈরি করেছি । এখন অ্যারের সবচেয়ে শেষের Index এর Value-র সাথে  Root নোডের Value কে Swap করবো এবং আবার Check করবো ট্রি এর Heap Property ঠিক আছে কিনা । এক্ষেত্রে Swap এর সময় Root বা Parent নোডটি যদি Child নোড থেকে ছোট হয় তবে Child নোডের Value দুটির মধ্যে যেটি বড় তার সাথে Parent নোডের Value টি Swap হবে ।

নিচের অ্যানিমেশন থেকে Heap Sort এর পুরো প্রক্রিয়াটি ভালোভাবে বোঝা যাবে ঃ

অ্যানিমেশনে হিপ সর্ট

কোড ইমপ্লিমেন্টেশন ঃ





কোড কমপ্লেক্সিটি ঃ O(nlogn)

রেফারেন্স ঃ

• Introduction to Algorithms
• Animation is taken from Wikipedia

হ্যাপি কোডিং ঃ