হিপ সর্ট: সংশোধিত সংস্করণের মধ্যে পার্থক্য

{{তথ্যছক অ্যালগরিদম|class=[[Sorting algorithm]]|image=[[Image:Sorting heapsort anim.gif]]|caption=এলোমেলোভাবে অনুমতিপ্রাপ্ত মানের একটি অ্যারে বাছাই করে হিপসোর্টের একটি রান দেখানো হয়েছ. অ্যালগরিদমের প্রথম পর্যায়ে ,অ্যারে উপাদানগুলিকে [[হিপ (ডেটা স্ট্রাকচার) | হিপ বৈশিষ্ট্য ]] পূরণ করার জন্য পুনরায় সাজানো হয়. প্রকৃত সর্টিং এর আগে, হিপ ট্রি কাঠামো চিত্রের জন্য সংক্ষেপে দেখানো হলো.|data=[[Array data structure|Array]]|time=<math>O(n\log n)</math>|average-time=<math>O(n\log n)</math>|best-time=<math>O(n\log n)</math> (distinct keys)<br />or <math>O(n)</math> (equal keys)|space=<math>O(n)</math> total <math>O(1)</math> auxiliary}}[[কম্পিউটার বিজ্ঞান|কম্পিউটার]] বিজ্ঞানে '''হিপসর্টটি''' একটি তুলনা ভিত্তিক [[সর্টিং অ্যালগোরিদম|বাছাইকরণ অ্যালগরিদম]] । হিপসর্টটি সিলেকশন সর্ট এর উন্নত ধরণধরন হিসাবে বিবেচনা করা যেতে পারে:সিলেকশন সর্ট এর মতো হিপসর্টটি তার ইনপুটটিকে একটি সাজানো এবং একটি অসাজানো অঞ্চলে বিভক্ত করে এবং এটি পুনরাবৃত্তিকভাবে অসাজানো অঞ্চল থেকে বৃহত্তম উপাদানটি বের করে অঞ্চলটিকে ছোট করে এবং সাজানো অঞ্চলে সন্নিবেশ করে। সিলেকশন সর্ট এর মতো , হিপসর্টটি অসাজানো অঞ্চলের লিনিয়ার-সময় স্ক্যানের সাথে সময় নষ্ট করে না,বরং, প্রতিটি ধাপে সবচেয়ে বড় উপাদানটি আরও দ্রুত খুঁজে পেতে হিপসর্টটি সিলেকশন সর্ট এর উন্নত ধরণহিপসর্টটিধরনহিপসর্টটি অসাজানো অঞ্চলকে হিপ নামক ডেটা স্ট্রাকচারে বজায় রাখে। <ref>{{বই উদ্ধৃতি|শিরোনাম=The Algorithm Design Manual|ইউআরএল=https://archive.org/details/algorithmdesignm00skie_676|শেষাংশ=Skiena|প্রথমাংশ=Steven|বছর=2008|প্রকাশক=Springer|পাতা=[https://archive.org/details/algorithmdesignm00skie_676/page/n120 109]|অধ্যায়=Searching and Sorting|doi=10.1007/978-1-84800-070-4_4|আইএসবিএন=978-1-84800-069-8}}</ref>

হিপসর্টটি ১৯৪64 সালে জে.ডাব্লু .জে উইলিয়ামস আবিষ্কার করেছিলেন। <ref>{{Harvard citation no brackets|Williams|1964}}</ref> এই সময়ে হিপের ও সূচনা হয় এবং উইলিয়ামস নিজস্ব একটি দরকারী ডেটা স্ট্রাকচার হিসাবে হিপকে উপস্থাপণ করেন । <ref name="brass">{{বই উদ্ধৃতি|শিরোনাম=Advanced Data Structures|ইউআরএল=https://archive.org/details/advanceddatastru00bras_251|শেষাংশ=Brass|প্রথমাংশ=Peter|বছর=2008|প্রকাশক=Cambridge University Press|পাতা=[https://archive.org/details/advanceddatastru00bras_251/page/n219 209]|আইএসবিএন=978-0-521-88037-4}}</ref> একই বছরে, [[রবার্ট বব ফ্লয়েড|আর.ডাব্লু .ফ্লোয়েড]] ট্রি হিপসর্টটি সিলেকশন সর্ট এর উন্নত ধরণধরন হিসাবে বিবেচনা করা যেতে পারে: সিলেকশন সর্ট এর মতো হিপসর্টটি তার ইনপুটটিকে একটি সাজানো এবং একটি অসাজানো অঞ্চলে বিভক্ত করে এবং এটি পুনরাবৃত্তিকভাবে অসাজানো অঞ্চল থেকে বৃহত্তম উপাদানটি বের করে অঞ্চলটিকে ছোট করে এবং সাজানো অঞ্চলে সন্নিবেশ করে।সর্ট [[সর্টিং অ্যালগোরিদম|অ্যালগরিদমে]] নিজের গবেষণা অব্যহত রেখে একটি উন্নত সংস্করণ প্রকাশ করেছেন যা একটি অ্যারেকে ইন-প্লেস সর্ট করতে পারে।