পাইথনে হিপ সর্ট কি?

Heap Sort হল বাইনারি হিপ ডেটা স্ট্রাকচারের উপর ভিত্তি করে সাজানোর কৌশল। হিপ সাজানোর সাথে এগিয়ে যাওয়ার জন্য, আপনাকে বাইনারি ট্রি এবং বাইনারি হিপের সাথে পরিচিত হতে হবে।

একটি সম্পূর্ণ বাইনারি গাছ কি?

একটি সম্পূর্ণ বাইনারি ট্রি হল একটি ট্রি ডেটা স্ট্রাকচার যেখানে শেষটি ব্যতীত সমস্ত স্তর সম্পূর্ণরূপে পূর্ণ হয়। শেষ স্তরটি অবশ্যই বাম দিক থেকে পূরণ করতে হবে।

বাইনারি হিপ কি?

বাইনারি হিপ বাইনারি গাছের একটি বিশেষ কেস। বাইনারি হিপ দুই ধরনের হয় -

• সর্বোচ্চ হিপ − প্রতিটি স্তরে প্যারেন্ট নোড তার চাইল্ড নোডের চেয়ে বড়৷

  ৷

• মিন হিপ − প্রতিটি স্তরে প্যারেন্ট নোড তার চাইল্ড নোডের থেকে ছোট৷

  ৷

সম্পূর্ণ বাইনারি গাছের অ্যারে প্রতিনিধিত্ব

বাইনারি হিপটিকে একটি অ্যারে হিসাবে উপস্থাপন করা যেতে পারে যেহেতু এটি স্থান দক্ষ। যদি প্যারেন্ট নোডটি সূচক I এ সংরক্ষিত থাকে, তাহলে বাম শিশুটি 2 * i + 1 দ্বারা এবং ডান শিশুটিকে 2 *i + 2 দ্বারা গণনা করা যেতে পারে। ধরে নেওয়া হচ্ছে, সূচকটি 0 থেকে শুরু হয়।

হিপ সাজানোর অ্যালগরিদম

• একটি সম্পূর্ণ বাইনারি গাছ থেকে সর্বোচ্চ হিপ তৈরি করুন।

• রুটটি সরান এবং স্তূপের শেষ উপাদানটির সাথে এটি প্রতিস্থাপন করুন, স্তূপের আকার 1 দ্বারা হ্রাস করুন এবং অবশিষ্ট নোডগুলি থেকে আবার একটি সর্বোচ্চ স্তূপ তৈরি করুন৷

• ধাপ 2 পুনরাবৃত্তি করুন যতক্ষণ না আমাদের শুধুমাত্র 1 নোড বাকি থাকে।

একটি সম্পূর্ণ বাইনারি গাছ থেকে সর্বোচ্চ হিপ তৈরি করুন

এটি একটি সম্পূর্ণ বাইনারি ট্রি থেকে সর্বোচ্চ হিপ তৈরির কোড, যেখানে দুটি চাইল্ড নোডকে মূলের সাথে তুলনা করা হয়। যদি বড় উপাদানটি রুট না হয় তবে রুটটির সাথে বড় উপাদানটি অদলবদল করুন। এটি একটি পুনরাবৃত্ত পদ্ধতি। বর্তমান রুট যা এর চাইল্ড নোডের চেয়ে ছোট তার সঠিক অবস্থানে না পৌঁছালে তার নিচের সাবট্রির সাথে ক্রমাগত তুলনা করা হয়।

নিম্নলিখিত কোডটি একটি সম্পূর্ণ বাইনারি ট্রি থেকে সর্বাধিক হিপ তৈরি করে যা মূলত অ্যারে যা আমরা সাজাতে চাই৷

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)

হিপ সর্ট

এই সময়ে, আমরা আমাদের সাথে সর্বোচ্চ গাদা আছে. এখন আমাদের নিম্নলিখিত কাজগুলো করতে হবে।

• হিপের শেষ উপাদানটির সাথে রুটটি অদলবদল করুন।

• স্তূপের আকার 1 দ্বারা হ্রাস করুন। (এর মানে হল যে বৃহত্তম উপাদানটি শেষ অবস্থানে পৌঁছেছে, আমাদের সেই উপাদানটিকে বিবেচনায় নেওয়ার দরকার নেই)।

• শেষ উপাদান বাদ দিয়ে সর্বোচ্চ হিপ পুনর্নির্মাণ করুন।

• উপরের ধাপগুলি পুনরাবৃত্তি করুন যতক্ষণ না আমাদের কাছে শুধুমাত্র 1টি উপাদান অবশিষ্ট থাকে।

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=' ')

সময়ের জটিলতা - O(n লগন)