হীপ (Heap)
হীপ হল একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা একটি পূর্ণ বাইনারি ট্রি হিসাবে গঠিত। হীপ সাধারণত দুটি প্রকারে বিভক্ত:
ম্যাক্স হীপ (Max Heap): যেখানে প্রতিটি নোডের মান তার সন্তানের মানের তুলনায় বড় বা সমান হয়। অর্থাৎ, শীর্ষ নোড সর্বাধিক মান ধারণ করে।
মিন হীপ (Min Heap): যেখানে প্রতিটি নোডের মান তার সন্তানের মানের তুলনায় ছোট বা সমান হয়। অর্থাৎ, শীর্ষ নোড সর্বনিম্ন মান ধারণ করে।
হীপ মূলত অ্যারেতে ব্যবহার করা হয়, এবং এর গঠন এবং অ্যাক্সেসের জন্য বিশেষ নিয়ম থাকে।
হীপের বৈশিষ্ট্য
- কনসিস্টেন্ট গঠন: হীপে সব স্তরে নোডগুলি সম্পূর্ণভাবে পূর্ণ থাকে (অর্থাৎ, কোন স্তর ফাঁকা থাকে না)।
- অপারেশন: হীপের জন্য প্রধান অপারেশনগুলো হল
insert,delete, এবংpeek(শীর্ষ নোডের মান দেখা)।
উদাহরণ (Python):
import heapq
# একটি মিন হীপ তৈরি
min_heap = []
# উপাদান যোগ করা
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 3)
# শীর্ষ উপাদান দেখুন
print("Minimum element:", min_heap[0]) # 2
# উপাদান মুছুন
min_element = heapq.heappop(min_heap) # 2
print("Removed element:", min_element)
# বর্তমান হীপ
print("Current heap:", min_heap) # [3, 5]
হীপ সর্ট (Heap Sort)
হীপ সর্ট একটি তুলনামূলক সর্টিং অ্যালগরিদম যা হীপ ডেটা স্ট্রাকচার ব্যবহার করে। এটি O(n log n) সময় জটিলতা নিয়ে কাজ করে এবং এটি ইন-প্লেস সর্টিং অ্যালগরিদম, যা অতিরিক্ত মেমরি ব্যবহার করে না।
কাজের প্রক্রিয়া:
- হীপ তৈরি: প্রথমে দেওয়া অ্যারেকে একটি হীপে রূপান্তর করুন (ম্যাক্স হীপ বা মিন হীপ).
- সাজানো:
- শীর্ষ নোড (সর্বাধিক বা সর্বনিম্ন)কে মুছে ফেলুন এবং অ্যারের শেষের দিকে রাখুন।
- হীপটি পুনরায় সাজান যাতে শীর্ষ নোড সর্বাধিক বা সর্বনিম্ন হয়।
- এই প্রক্রিয়া পুনরাবৃত্তি করুন যতক্ষণ না পুরো অ্যারে সাজানো হয়।
উদাহরণ (Python):
import heapq
def heap_sort(arr):
# 1. হীপ তৈরি করা
heapq.heapify(arr) # মিন হীপ তৈরি
# 2. সাজানো
sorted_array = []
while arr:
sorted_array.append(heapq.heappop(arr)) # শীর্ষ উপাদান বের করুন
return sorted_array
# ব্যবহার
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = heap_sort(arr)
print("Sorted array:", sorted_arr)
আউটপুট:
Sorted array: [11, 12, 22, 25, 34, 64, 90]
উপসংহার
হীপ একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা বিভিন্ন ধরনের অ্যাপ্লিকেশন, বিশেষ করে হীপ সর্টিং অ্যালগরিদমে ব্যবহৃত হয়। হীপ সর্ট কার্যকরী এবং ইন-প্লেস সর্টিং পদ্ধতি, যা গতি এবং মেমরি ব্যবস্থাপনার জন্য একটি ভালো সমাধান। এই ধারণাগুলি প্রোগ্রামিং এবং ডেটা স্ট্রাকচার ব্যবস্থাপনায় গুরুত্বপূর্ণ ভূমিকা পালন করে।
