ডাটা স্ট্রাকচার - ১১ঃ হিপসর্ট

হিপ পদ্ধতি অবলম্বন করে যে ধরনের সর্ট করা হয় তাকেই হিপ সর্ট বলে। আমরা জানি হিপে রুট নোডটা থাকে সবচেয়ে বড়। হিপ সর্টে সেই রুট নোডটাকে সবার শেষের নোডের সাথে সোয়াপ করা হয়। তারপর শেষের নোডটা বাদ দিয়ে পুরো ট্রি টাকে আবার হিপে রুপান্তর করা হয়। এভাবে সোয়াপ এবং হিপে রুপান্তরের এক পর্যায়ে পুরো ট্রি টা সর্ট হয়ে যায়। নীচের সিমুলেশনটা খেয়াল করো-

সোয়াপ করার পর প্রতিবার আমরা শেষ থেকে একটা করে নোড বাদ দিয়ে বাকি অংশটাকে হিপিফাই করতেছি। এভাবে একটা পর্যায়ে গিয়ে পুরো ট্রি টাই সর্ট হয়ে যায়। কোডে রুপান্তর আরো সোজা-

 void heapSort(int heap[], int heapSize)  
 {  
   int i, temp;  
   buildMaxHeap(heap, heapSize); //Building heap  
   for(i = heapSize; i>1; i--)  
   {  
     temp = heap[1];  
     heap[1] = heap[heapSize];  
     heap[heapSize] = temp;  
     heapSize--;  
     maxHefipy(heap, heapSize, 1);  
   }  
 }