হিপ সর্ট

কম্পিউটার বিজ্ঞানে হিপসর্টটি একটি তুলনা ভিত্তিক বাছাইকরণ অ্যালগরিদম । হিপসর্টটি সিলেকশন সর্ট এর উন্নত ধরন হিসাবে বিবেচনা করা যেতে পারে:সিলেকশন সর্ট এর মতো হিপসর্টটি তার ইনপুটটিকে একটি সাজানো এবং একটি অসাজানো অঞ্চলে বিভক্ত করে এবং এটি পুনরাবৃত্তিকভাবে অসাজানো অঞ্চল থেকে বৃহত্তম উপাদানটি বের করে অঞ্চলটিকে ছোট করে এবং সাজানো অঞ্চলে সন্নিবেশ করে। সিলেকশন সর্ট এর মতো , হিপসর্টটি অসাজানো অঞ্চলের লিনিয়ার-সময় স্ক্যানের সাথে সময় নষ্ট করে না,বরং, প্রতিটি ধাপে সবচেয়ে বড় উপাদানটি আরও দ্রুত খুঁজে পেতে হিপসর্টটি সিলেকশন সর্ট এর উন্নত ধরনহিপসর্টটি অসাজানো অঞ্চলকে হিপ নামক ডেটা স্ট্রাকচারে বজায় রাখে। 
যদিও বেশিরভাগ মেশিনে একটি সু-বাস্তবায়িত কুইক সর্ট এর তুলনায় অনুশীলনে হিপসর্টটি কিছুটা ধীর গতিযুক্ত, এটির ব্যবহারে সবচেয়ে বাজে রানটাইমের ক্ষেত্রে O(এন লগ এন ) সুবিধা রয়েছে। হিপসর্ট একটি ইন-প্লেস অ্যালগরিদম, তবে এটি কোন স্থিতিশীল সর্ট ও নয়।
হিপসর্টটি ১৯৪64 সালে জে.ডাব্লিউ .জে উইলিয়ামস আবিষ্কার করেছিলেন। এই সময়ে হিপের ও সূচনা হয় এবং উইলিয়ামস নিজস্ব একটি দরকারী ডেটা স্ট্রাকচার হিসাবে হিপকে উপস্থাপণ করেন । একই বছরে, আর.ডাব্লিউ .ফ্লোয়েড ট্রি হিপসর্টটি সিলেকশন সর্ট এর উন্নত ধরন হিসাবে বিবেচনা করা যেতে পারে: সিলেকশন সর্ট এর মতো হিপসর্টটি তার ইনপুটটিকে একটি সাজানো এবং একটি অসাজানো অঞ্চলে বিভক্ত করে এবং এটি পুনরাবৃত্তিকভাবে অসাজানো অঞ্চল থেকে বৃহত্তম উপাদানটি বের করে অঞ্চলটিকে ছোট করে এবং সাজানো অঞ্চলে সন্নিবেশ করে।সর্ট অ্যালগরিদমে নিজের গবেষণা অব্যহত রেখে একটি উন্নত সংস্করণ প্রকাশ করেছেন যা একটি অ্যারেকে ইন-প্লেস সর্ট করতে পারে।
হিপসর্ট অ্যালগরিদমকে দুটি ভাগে ভাগ করা যায়।
প্রথম ধাপে, একটি হিপ ডেটা থেকে তৈরি করা হয় ( দেখুন বাইনারি হিপ এবং হিপ তৈরি)। হিপকে প্রায়ই সম্পূর্ণ বাইনারি ট্রি এর বিন্যাস সহ একটি অ্যারেতে রাখা হয়। সম্পূর্ণ বাইনারি ট্রি বাইনারি ট্রি কাঠামোটিকে অ্যারে ইনডেক্স গুলিতে ম্যাপ করে। প্রতিটি অ্যারে ইনডেক্স একটি নোড প্রতিনিধিত্ব করে।নোডের পিতামাতা, বাম চাইল্ড শাখা বা ডান চাইল্ড শাখার ইনডেক্স এগুলো সাধারণ অভিব্যক্তি। শূন্য-ভিত্তিক অ্যারের জন্য রুট নোডকে 0 ইনডেক্সে সর্ট করা হয়; যদি codice_1 বর্তমান নোডের ইনডেক্স হয়, তবে
দ্বিতীয় ধাপে, বার বার হিপ থেকে সবচেয়ে বড় উপাদানটিকে (হিপ এর রুট) সরিয়ে এবং অ্যারেতে প্রবেশ করিয়ে একটি সর্টেড অ্যারে তৈরি করা হয়। হিপ বৈশিষ্ট্য বজায় রাখতে প্রতিটি অপসারণের পরে হিপ পরিবর্তন করা হয়। একবার সমস্ত অবজেক্ট হিপ থেকে সরানো হয়ে গেলে যে অ্যারেটি পাবো সেটি সর্টেড অ্যারে হবে।
হিপসর্ট দিয়ে একটি অ্যারে ব্যবহার করেই সর্ট এর কাজ করা যায় । অ্যারেটিকে দুটি ভাগে ভাগ করা যায়, সর্টেড অ্যারে এবং হিপ। অ্যারে হিসাবে হিপ এর স্টোরেজটি এখানে চিত্রে দেখানো হলো। হিপ এর ইনভ্যারিয়্যান্ট প্রতিটি নিষ্কাশনের পরে সংরক্ষণ করা হয়, তাই নিষ্কাশন পদ্ধতিটাই একমাত্র বিবেচনার বিষয়।
হিপসর্ট অ্যালগরিদমে প্রথমে লিস্টকে মাক্স হিপে পরিণত করা হয় । অ্যালগরিদমটি তারপরে বারবার লিস্টের প্রথম মানটিকে সর্বশেষ মান দিয়ে প্রতিস্থাপন করে, এভাবে হিপ অপারেশনে বিবেচিত মানের পরিসরকে এক এক করে হ্রাস করে এবং নতুন প্রথম মানটিকে হিপের নিজস্ব অবস্থানে স্থানপরিবর্তন করে। বিবেচিত মানগুলির ব্যাপ্তি দৈর্ঘ্যের মান এক না হওয়া পর্যন্ত অপারেশনটি পুনরাবৃত্তিকভাবে চলতে থাকে।
পদক্ষেপগুলি হ'ল:
বিল্ডম্যাক্সহিপ () অপারেশনটি একবার চালানো হয় এবং এটি অর্ডার (এন) এ সম্পন্ন হয়। শিফ্টডাউন () ফাংশনটি ও O(log এন ) এ সম্পন্ন হয় এবং এন বার কল করা হয় ।সুতরাং, এই অ্যালগরিদমের কার্যকারিতা হ'ল O(এন + এন লগ এন ) = O ( এন লগ এন ) ।
স্যুডোকোডে অ্যালগরিদমটি প্রয়োগ করার জন্য নিম্নলিখিতটি একটি সহজ উপায় আছে। অ্যারেগুলি শূন্য-ভিত্তিক এবং অ্যারের দুটি উপাদান বিনিময় করতে codice_2 আন্দোলন 'ডাউন' অর্থ রুট থেকে লিভ্সের দিকে যাওয়া, বা নিম্ন ইনডেক্স থেকে উচ্চতর ইনডেক্সের দিকে যাওয়া। মনে রাখবেন যে সর্টের সময়, বৃহত্তম উপাদানটি codice_3 তে হিপের রুট এ থাকে,সর্ট শেষে, বৃহত্তম উপাদানটি codice_4 ।
<nowiki>সর্টিং</nowiki> codice_5 এবং codice_6 codice_7 প্রক্রিয়া মাধ্যমে codice_8 । codice_5 বাস্তবায়নের জন্য সাধারণ স্থানে থাকা হিপ তৈরিতে while লুপ
codice_5 পদ্ধতিটি <nowiki>হিপ</nowiki> বৈশিষ্ট্যটি প্রতিষ্ঠার জন্য ধারাবাহিকভাবে নীচের দিকে অগ্রসর হয়ে নীচ থেকে উপরে একটি হিপ নির্মাণ হিসাবে ভাবা যেতে পারে। একটি বিকল্প সংস্করণ আছে যা আরও বোধগম্য হতে পারে (নীচে দেখানো হয়েছে) সেটি হল হিপ টপ-ডাউন তৈরি করা এবং উপরের দিকে codice_13 করা । এই "codice_14" সংস্করণটি খালি হিপ দিয়ে শুরু করে এবং ধারাবাহিকভাবে উপাদানগুলিকে সন্নিবেশ করে যেখানে উপরে বর্ণিতcodice_15 সম্পূর্ণ ইনপুট অ্যারেটিকে পরিপূর্ণ হিসেবে বিবেচনা করে তবে শেষ তুচ্ছ উপহিপ( শেষ প্যারেন্ট নোড) থেকে শুরু করে হিপকে ভাঙতে এবং মেরামত করতে থাকে ।
এছাড়াও, "codice_16"codice_17 সংস্করণে O ( এন ) টাইম কমপ্লেক্সিটি রয়েছে, যখন নীচে উল্লেখিতcodice_13ডাউন সংস্করণে প্রতিটি উপাদান একবারে একটি করে সন্নিবেশ করার কারণে টাইম কমপ্লেক্সিটি হয় O ( এন লগ এন ) । এটি পাল্টা স্বজ্ঞাত হিসাবে মনে হতে পারে, এক নজরে, এটা স্পষ্ট যে আগেরটি তার লগারিথমিক-সময় শিফিং ফাংশনটিকে পরবর্তীর তুলনায় অর্ধেক কল করে; অর্থাৎ, এগুলি কেবল একটি ধ্রুবক ফ্যাক্টর দ্বারা পৃথক বলে মনে হয়, যা কখনই অ্যাসিম্পটোটিক বিশ্লেষণকে প্রভাবিত করে না।
কমপ্লেক্সিটির এই পার্থক্যের পিছনের অন্তর্দৃষ্টি উপলব্ধি করার জন্য, মনে রাখবেন যে কোনও একটি codice_13আপ কল চলাকালীন ঘটে যাওয়া swap সংখ্যা "নোডের ডেপ্থ বৃদ্ধির সাথে সাথে বৃদ্ধি পায়" যেখানে কল করা হয়। সমস্যা হ'ল একটি হিপে "shallow" নোডের তুলনায় "deep" নোডের সংখ্যা অনেক বেশি(তাত্পর্যপূর্ণভাবে) , যাতে হিপের নীচে বা এর কাছাকাছি নোডগুলিতে আনুমানিক লিনিয়ার সংখ্যক কল করার সময় codice_13আপ এর সম্পূর্ণ লগারিথমিক রানিং সময় থাকতে পারে । অন্যদিকে, যে কোনও codice_13আপ কল চলাকালীন ঘটে যাওয়া swap সংখ্যা যে নোডের উপরে কল করা হয় তার "ডেপ্থ" বৃদ্ধি "সাথে সাথে হ্রাস পায়" । সুতরাং, যখন "codice_16"codice_17 codice_5 শুরু হয় এবং নীচের সবচেয়ে বেশি সংখ্যক নোড-স্তরসমূহ থেকে"codice_16"codice_26 কল করে, প্রত্যেকবার "codice_27" , সর্বাধিক swap এর সংখ্যা যে "নোড থেকে codice_28" "উচ্চতা" (হিপের নীচ থেকে) এর সমান হয় । অন্য কথায়, "codice_16"codice_30 প্রায় অর্ধেক কলগুলির মধ্যে সর্বাধিক মাত্র একটি swap হবে, তারপরে প্রায় চতুর্থাংশ কলগুলির মধ্যে কমপক্ষে দুইটি swap হবে ইত্যাদি .
হিপসর্ট অ্যালগরিদম নিজেই হিপিফাইয়ের উভয় সংস্করণ ব্যবহার করে টাইম কমপ্লেক্সিটি O ( এন লগ এন) রাখে।