হিপ সর্ট (Heap Sort) হলো বাইনারি হিপ (binary heap) ডেটা স্ট্রাকচার-ভিত্তিক একটি সর্টিং টেকনিক। হিপ সর্ট বুঝতে হলে আপনাকে বাইনারি ট্রি (binary tree) এবং বাইনারি হিপ (binary heap) সম্পর্কে জানতে হবে।
কমপ্লিট বাইনারি ট্রি (Complete Binary Tree) কী?
একটি কমপ্লিট বাইনারি ট্রি হলো একটি ট্রি ডেটা স্ট্রাকচার যেখানে লাস্ট লেভেল ছাড়া সকল লেভেল সম্পূর্ণভাবে ভরা থাকে। লাস্ট লেভেল অবশ্যই বাম দিক থেকে ভরা হয়।
বাইনারি হিপ (Binary Heap) কী?
বাইনারি হিপ হলো বাইনারি ট্রির একটি বিশেষ কেস। বাইনারি হিপ দুটি প্রকারের হয়:
Max Heap - প্রতিটি লেভেলে পেরেন্ট নোড এর চাইল্ড নোডগুলো থেকে বড়।
Min Heap - প্রতিটি লেভেলে পেরেন্ট নোড এর চাইল্ড নোডগুলো থেকে ছোট।
কমপ্লিট বাইনারি ট্রির অ্যারে রিপ্রেজেন্টেশন
বাইনারি হিপকে অ্যারে হিসেবে রিপ্রেজেন্ট করা যায় কারণ এটি স্পেস-ইফিশিয়েন্ট। যদি পেরেন্ট নোড ইনডেক্স i-তে সংরক্ষিত থাকে, তবে লেফট চাইল্ড ক্যালকুলেট করা যায় 2 * i + 1 দিয়ে এবং রাইট চাইল্ড 2 * i + 2 দিয়ে। এখানে ধরা হয়েছে ইনডেক্স ০ থেকে শুরু হয়।
হিপ সর্ট অ্যালগরিদম (Heap Sort Algorithm)
কমপ্লিট বাইনারি ট্রি থেকে ম্যাক্স হিপ (max heap) তৈরি করুন।
রুট (root) সরিয়ে সেটিকে হিপের লাস্ট এলিমেন্ট দিয়ে রিপ্লেস করুন, হিপের সাইজ ১ কমানো এবং বাকি নোডগুলোর থেকে আবার ম্যাক্স হিপ তৈরি করুন।
ধাপ ২ পুনরাবৃত্তি করুন যতক্ষণ না ১টি নোড বাকি থাকে।
কমপ্লিট বাইনারি ট্রি থেকে ম্যাক্স হিপ তৈরি করা
নিচে কমপ্লিট বাইনারি ট্রি থেকে ম্যাক্স হিপ তৈরির কোড দেওয়া হলো, যেখানে দুটি চাইল্ড নোড রুটের সাথে তুলনা করা হয়। যদি বড় এলিমেন্টটি রুট না হয়, তবে বড় এলিমেন্টটিকে রুটের সাথে সোয়াপ করুন। এটি একটি রিকার্সিভ প্রসিডিউর। বর্তমান রুট যা তার চাইল্ড নোডগুলোর চেয়ে ছোট, সেটি liên tục তার লোয়ার সাবট্রিয়ের সাথে তুলনা করা হয় যতক্ষণ না সেটি তার সঠিক পজিশনে পৌঁছায়।
নিচের কোডটি একটি কমপ্লিট বাইনারি ট্রি থেকে ম্যাক্স হিপ তৈরি করে যা মূলত সে অ্যারে যা আমরা সর্ট করতে চাই।
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
হিপ সর্ট (Heap Sort)
এই সময়, আমাদের কাছে ম্যাক্স হিপ আছে। এখন আমাদের নিচের কাজগুলো করতে হবে।
রুটকে হিপের লাস্ট এলিমেন্টের সাথে সোয়াপ করুন।
হিপের সাইজ ১ কমানো। (এটি বোঝায় যে সবচেয়ে বড় এলিমেন্টটি লাস্ট পজিশনে পৌঁছেছে, আমাদের সেটিকে আর বিবেচনা করতে হবে না)।
লাস্ট এলিমেন্ট বাদ দিয়ে আবার ম্যাক্স হিপ রিবিল্ড করুন।
উপরের ধাপগুলো পুনরাবৃত্তি করুন যতক্ষণ না ১টি এলিমেন্ট বাকি থাকে।
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
পাইথনে হিপ সর্টের সম্পূর্ণ প্রোগ্রাম নিচে দেওয়া হলো:
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=' ')
TIME COMPLEXITY - O(n logn)
