একটি হিপকে 'আংশিকভাবে সাজানো' হিসাবে উল্লেখ করা হয় এবং 'আংশিকভাবে সাজানো' নয়। 'সর্ট' শব্দের অর্থ সম্পূর্ণ ক্রম (সম্পূর্ণ সাজানো)। একটি গাদা আংশিকভাবে নির্বিচারে আদেশ করা হয় না. একটি স্তূপ আংশিকভাবে একটি মানদণ্ড (প্যাটার্ন) অনুসরণ করে সাজানো হয়েছে, যেমনটি নীচে দেখানো হয়েছে।
সুতরাং, heapsort দুটি পর্যায় নিয়ে গঠিত: স্তূপ তৈরি করা এবং স্তূপের উপরে থেকে আদেশকৃত উপাদান বের করা। দ্বিতীয় পর্যায়ে, প্রতিটি নিষ্কাশনের পরে, স্তূপটি পুনরায় তৈরি করা হয়। প্রতিটি পুনর্নির্মাণ মূল বিল্ডিং প্রক্রিয়ার চেয়ে দ্রুততর কারণ পুনর্নির্মাণ পূর্ববর্তী বিল্ড থেকে করা হয়, যেখানে একটি উপাদান সরানো হয়েছে। এবং যে সঙ্গে, heapsort একটি সম্পূর্ণরূপে সাজানো তালিকা সাজান.
এই নিবন্ধটির উদ্দেশ্য হল সংক্ষিপ্তভাবে হেপসর্ট ব্যাখ্যা করা এবং তারপরে এর সময় জটিলতা তৈরি করা (নীচে সময় জটিলতার অর্থ দেখুন)। শেষের দিকে, C++ এ কোডিং করা হয়।
ন্যূনতম স্তূপ
একটি স্তূপ একটি সর্বনিম্ন গাদা বা সর্বোচ্চ গাদা হতে পারে। ম্যাক্স-হিপ হল এমন একটি যেখানে প্রথম উপাদানটি সর্বোচ্চ উপাদান এবং পুরো ট্রি বা সংশ্লিষ্ট তালিকাটি আংশিকভাবে অবরোহ ক্রমে সাজানো হয়। একটি মিন-হিপ হল এমন একটি যেখানে প্রথম উপাদানটি সর্বনিম্ন উপাদান, এবং পুরো তালিকাটি আংশিকভাবে আরোহী ক্রমে সাজানো হয়। এই নিবন্ধে, শুধুমাত্র সর্বনিম্ন গাদা বিবেচনা করা হয়. দ্রষ্টব্য: হিপের বিষয়ে, একটি উপাদানকে নোডও বলা হয়।
একটি গাদা একটি সম্পূর্ণ বাইনারি গাছ। বাইনারি ট্রি একটি অ্যারে (তালিকা) হিসাবে প্রকাশ করা যেতে পারে; উপরে থেকে নীচে এবং বাম থেকে ডানে পড়ুন। একটি মিন-হিপের হিপ বৈশিষ্ট্য হল যে একটি প্যারেন্ট নোড তার দুটি সন্তানের প্রতিটির থেকে কম বা সমান। একটি অবিন্যস্ত তালিকার একটি উদাহরণ হল:
9 | 19 | 24 | 5 | 3 | এগারো | 14 | 22 | 7 | 6 | 17 | পনের | শূন্য | শূন্য | শূন্য |
0 | 1 | দুই | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | এগারো | 12 | 13 | 14 |
এই টেবিলের প্রথম সারিটি অ্যারের উপাদান। দ্বিতীয় সারিতে শূন্য-ভিত্তিক সূচক রয়েছে। উপাদানগুলির এই তালিকাটিকে একটি গাছ হিসাবে প্রকাশ করা যেতে পারে। একটি সম্পূর্ণ বাইনারি গাছ তৈরি করতে নাল উপাদান যোগ করা হয়েছে। কঠোরভাবে বলতে গেলে, শূন্য উপাদানগুলি তালিকার (বৃক্ষ) অংশ নয়। এই তালিকার কোন অর্ডার নেই, তাই এটি এখনও একটি গাদা নয়। এটি একটি গাদা হয়ে যাবে যখন এটির আংশিক ক্রম ছিল, গাদা সম্পত্তি অনুযায়ী।
নোড এবং সূচকের মধ্যে সম্পর্ক
মনে রাখবেন, হিপ কনফিগারেশন (হিপ প্রপার্টি) হওয়ার আগে একটি হিপ হল একটি সম্পূর্ণ বাইনারি ট্রি। পূর্ববর্তী তালিকাটি এখনও একটি গাদা নয়, কারণ উপাদানগুলি হিপ সম্পত্তি মেনে চলে না। মিন-হিপ প্রপার্টি অনুসারে উপাদানগুলিকে আংশিক ক্রমে পুনর্বিন্যাস করার পরে এটি একটি গাদা হয়ে যায়। আংশিক ক্রম আংশিক বাছাই হিসাবে দেখা যেতে পারে (যদিও 'বাছাই' শব্দের অর্থ সম্পূর্ণ ক্রম)।
একটি বাইনারি গাছ একটি স্তূপ হোক বা না হোক, প্রতিটি পিতামাতার দুটি সন্তান রয়েছে, পাতা (শেষ) নোডগুলি ছাড়া৷ প্রতিটি পিতামাতা এবং তার সন্তানদের মধ্যে সূচকগুলির মধ্যে একটি গাণিতিক সম্পর্ক রয়েছে। এটি নিম্নরূপ: যদি পিতামাতা সূচী i এ থাকে, তবে বাম সন্তানটি সূচকে থাকে:
দুই * i + 1এবং সঠিক শিশুটি সূচকে রয়েছে:
দুই * i + দুইএটি শূন্য-ভিত্তিক সূচীকরণের জন্য। এবং তাই, সূচক 0-এ একজন পিতা-মাতার বাম সন্তান সূচক 2×0+1=1 এবং ডান সন্তান 2×0+2=2। সূচক 1-এ একজন পিতা-মাতার বাম সন্তান রয়েছে সূচক 2×1+1=3 এবং ডান সন্তান সূচক 2×1+2=4; এবং তাই
মিন-হিপ প্রপার্টি অনুসারে, i-এ একজন অভিভাবক 2i+1-এ বাম সন্তানের থেকে কম বা সমান এবং 2i+2-এ ডান সন্তানের থেকে কম বা সমান।
গাদা
Heapifying মানে একটি স্তূপ নির্মাণ করা। এর অর্থ হল একটি তালিকার উপাদানগুলিকে (বা সংশ্লিষ্ট গাছের) পুনর্বিন্যাস করা যাতে তারা হিপ সম্পত্তিকে সন্তুষ্ট করে। heapifying প্রক্রিয়া শেষে, তালিকা বা গাছ একটি গাদা হয়.
যদি আগের সাজানো তালিকাটি হিপ করা হয়, তাহলে এটি হয়ে যাবে:
3 | 5 | এগারো | 7 | 6 | পনের | 14 | 22 | 9 | 19 | 17 | 24 | শূন্য | শূন্য | শূন্য |
0 | 1 | দুই | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | এগারো | 12 | 13 | 14 |
দ্রষ্টব্য: তালিকায় 12টি উপাদান রয়েছে এবং 15টি নয়। দ্বিতীয় সারিতে সূচী আছে. গাদা তৈরির প্রক্রিয়ায়, উপাদানগুলি পরীক্ষা করতে হয়েছিল এবং কিছু অদলবদল করতে হয়েছিল।
লক্ষ্য করুন যে ক্ষুদ্রতম এবং প্রথম উপাদানটি হল 3. বাকি উপাদানগুলি একটি আরোহী কিন্তু অপরিবর্তনীয় পদ্ধতিতে অনুসরণ করে। যদি 2i+1 এবং 2i+2 পজিশনে বাম এবং ডানের বাচ্চারা প্রত্যেকেই i-তে পিতামাতার থেকে বড় বা সমান হয়, তাহলে এটি একটি মিন-হিপ। এটি সম্পূর্ণ অর্ডার বা সাজানো নয়। এটি আংশিক ক্রম, গাদা সম্পত্তি অনুযায়ী. এখান থেকেই শুরু হয় হিপ সাজানোর পরবর্তী ধাপ।
Heapify সময় জটিলতা
সময়ের জটিলতা হল কিছু কোডের আপেক্ষিক চলমান সময়। কোডটি সম্পূর্ণ করার জন্য এটিকে প্রধান ক্রিয়াকলাপের সংখ্যা হিসাবে দেখা যেতে পারে। গাদা বিল্ডিং জন্য বিভিন্ন অ্যালগরিদম আছে. সবচেয়ে দক্ষ এবং দ্রুততম ধারাবাহিকভাবে তালিকাটিকে দুই দ্বারা ভাগ করে, নীচের দিক থেকে উপাদানগুলি পরীক্ষা করে এবং তারপরে উপাদানগুলির কিছু অদলবদল করে৷ ধরুন N হল তালিকার ব্যবহারিক উপাদানের সংখ্যা। এই অ্যালগরিদমের সাহায্যে, প্রধান ক্রিয়াকলাপগুলির সর্বাধিক সংখ্যা (অদলবদল) হল N। হেপিফাই করার সময় জটিলতা পূর্বে দেওয়া হয়েছিল:
ও ( n )যেখানে n হল N এবং প্রধান ক্রিয়াকলাপের সর্বাধিক সম্ভাব্য সংখ্যা। এই স্বরলিপিকে বিগ-ও স্বরলিপি বলা হয়। এটি বড় হাতের অক্ষরে O দিয়ে শুরু হয়, তারপরে বন্ধনী। বন্ধনীর ভিতরে সম্ভাব্য সর্বোচ্চ সংখ্যক ক্রিয়াকলাপের অভিব্যক্তি রয়েছে।
মনে রাখবেন: যোগ করা গুণিত হতে পারে যদি একই জিনিস যোগ করা হয় বারবার পুনরাবৃত্তি হয়।
হিপসর্ট ইলাস্ট্রেশন
আগের সাজানো তালিকাটি হিপসর্ট চিত্রিত করতে ব্যবহার করা হবে। প্রদত্ত তালিকা হল:
9 19 24 5 3 এগারো 14 22 7 6 17 পনেরতালিকা থেকে উৎপাদিত মিন-হিপ হল:
3 5 এগারো 7 6 পনের 14 22 9 19 17 24হিপসর্টের প্রথম পর্যায় হল হিপ তৈরি করা যা উত্পাদিত হয়েছে। এটি একটি আংশিক আদেশ তালিকা. এটি একটি সাজানো (সম্পূর্ণভাবে সাজানো) তালিকা নয়।
দ্বিতীয় ধাপে স্তূপ থেকে সর্বনিম্ন উপাদান, যেটি প্রথম উপাদান, অপসারণ করা, অবশিষ্ট স্তূপটিকে পুনরায় ঢেকে রাখা এবং ফলাফলের সর্বনিম্ন উপাদানগুলি সরানো। সর্বনিম্ন উপাদানটি সর্বদা পুনঃ-হ্যাপিফাইড হিপে প্রথম উপাদান। উপাদানগুলি সরানো এবং দূরে নিক্ষেপ করা হয় না। সেগুলিকে যে ক্রমে অপসারণ করা হয় সে অনুসারে একটি ভিন্ন অ্যারেতে পাঠানো যেতে পারে৷
শেষ পর্যন্ত, নতুন অ্যারে সমস্ত উপাদানগুলিকে ক্রমবর্ধমান ক্রমে (সম্পূর্ণভাবে) সাজানো থাকবে; এবং আর শুধু আংশিকভাবে আদেশ করা হয় না।
দ্বিতীয় পর্যায়ে, প্রথম কাজটি হল 3 সরিয়ে নতুন অ্যারেতে স্থাপন করা। ফলাফল হল:
3এবং
5 এগারো 7 6 পনের 14 22 9 19 17 24প্রথম উপাদান নিষ্কাশন করার আগে অবশিষ্ট উপাদানগুলিকে হেপিফাই করতে হবে। অবশিষ্ট উপাদানের গাদা হতে পারে:
5 6 7 9 পনের 14 22 এগারো 19 17 245 বের করা এবং নতুন তালিকা (অ্যারে) যোগ করা ফলাফল দেয়:
3 5এবং
6 7 9 পনের 14 22 এগারো 19 17 24অবশিষ্ট সেট হিপিফাই করা হবে:
6 7 9 পনের 14 22 এগারো 19 17 246 বের করা এবং নতুন তালিকা (অ্যারে) যোগ করা ফলাফল দেয়:
3 5 6এবং
7 9 পনের 14 22 এগারো 19 17 24অবশিষ্ট সেট হিপিফাই করা হবে:
7 9 এগারো 14 22 পনের 19 17 247 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7এবং
9 এগারো 14 22 পনের 19 17 24অবশিষ্ট সেটটি হিপিফাই করা দেয়:
9 এগারো 14 22 পনের 19 17 249 এক্সট্রাক্ট করা এবং নতুন তালিকায় যোগ করা, ফলাফল দেয়:
3 5 6 7 9এবং
এগারো 14 22 পনের 19 17 24অবশিষ্ট সেটটি হিপিফাই করা দেয়:
এগারো 14 17 পনের 19 22 2411 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7 9 এগারোএবং
14 17 পনের 19 22 24অবশিষ্ট সেট হিপিফাই করা হবে:
14 17 পনের 19 22 2414 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7 9 এগারো 14এবং
17 পনের 19 22 24অবশিষ্ট সেট হিপিফাই করা হবে:
পনের 17 19 22 2415 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7 9 এগারো 14 পনেরএবং
17 19 22 24অবশিষ্ট সেট হিপিফাই করা হবে:
17 19 22 2417 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7 9 এগারো 14 পনের 17এবং
19 22 24অবশিষ্ট সেট হিপিফাই করা হবে:
19 22 2419 এক্সট্র্যাক্ট করা এবং নতুন তালিকায় যোগ করা ফলাফল দেয়:
3 5 6 7 9 এগারো 14 পনের 17 19এবং
22 24অবশিষ্ট সেটটি হিপিফাই করা দেয়:
22 2422 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7 9 এগারো 14 পনের 17 19 22এবং
24অবশিষ্ট সেটটি হিপিফাই করা দেয়:
2424 বের করে নতুন তালিকায় যোগ করলে ফলাফল পাওয়া যায়:
3 5 6 7 9 এগারো 14 পনের 17 19 22 24এবং
- - -হিপ অ্যারে এখন খালি। শুরুতে যে সমস্ত উপাদান ছিল সেগুলি এখন নতুন অ্যারেতে (তালিকা) এবং সাজানো হয়েছে।
হিপসর্ট অ্যালগরিদম
যদিও পাঠক পাঠ্যপুস্তকে পড়ে থাকতে পারে যে heapsort দুটি পর্যায় নিয়ে গঠিত, তবুও heapsort একটি পর্যায় নিয়ে গঠিত হিসাবে দেখা যেতে পারে, যা প্রদত্ত অ্যারে থেকে পুনরাবৃত্তিমূলকভাবে সঙ্কুচিত হয়। এর সাথে, হেপসর্ট দিয়ে সাজানোর অ্যালগরিদমটি নিম্নরূপ:
- সাজানো না হওয়া তালিকার ভান্ডার।
- হিপের প্রথম উপাদানটি বের করুন এবং এটিকে নতুন তালিকার প্রথম উপাদান হিসাবে রাখুন।
- অবশিষ্ট তালিকা হিপিফাই.
- নতুন হিপের প্রথম উপাদানটি বের করুন এবং নতুন তালিকার পরবর্তী উপাদান হিসাবে রাখুন।
- হিপ তালিকা খালি না হওয়া পর্যন্ত ক্রমানুসারে পূর্ববর্তী ধাপগুলি পুনরাবৃত্তি করুন। শেষ পর্যন্ত নতুন তালিকা সাজানো হয়।
Heapsort সময় জটিলতা সঠিক
হেপসর্টের সময় জটিলতা নির্ধারণ করতে এক-পর্যায়ের পদ্ধতি ব্যবহার করা হয়। অনুমান করুন যে 8টি সাজানো না হওয়া উপাদানগুলি সাজানো হবে।
সম্ভাব্য সর্বাধিক সংখ্যক অপারেশনকে হেপিফাই করতে 8 উপাদান হয় 8 .দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন 7 উপাদান হয় 7 .
দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন 6 উপাদান হয় 6 .
দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন 5 উপাদান হয় 5 .
দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন 4 উপাদান হয় 4 .
দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন 3 উপাদান হয় 3 .
দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন দুই উপাদান হয় দুই .
দ্য বাকিগুলিকে হেপিফাই করার জন্য সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন 1 উপাদান হল 1 .
অপারেশনের সম্ভাব্য সর্বাধিক সংখ্যা হল:
8 + 7 + 6 + 5 + 4 + 3 + দুই + 1 = 36অপারেশনের এই সংখ্যাগুলির গড় হল:
36 / 8 = 4.5লক্ষ্য করুন যে পূর্ববর্তী চিত্রের শেষ চারটি স্তূপ পরিবর্তন হয়নি, যখন প্রথম উপাদানটি সরানো হয়েছিল। প্রথম উপাদানটি সরানোর সময় আগের কিছু গাদাও পরিবর্তন হয়নি। এর সাথে, প্রধান ক্রিয়াকলাপগুলির একটি ভাল গড় সংখ্যা (অদলবদল) 3 এবং 4.5 নয়। সুতরাং, প্রধান অপারেশনগুলির একটি ভাল মোট গড় সংখ্যা হল:
24 = 8 এক্স 3=> 24 = 8 এক্স লগ < উপ > দুই < / উপ > 8
লগ থেকে দুই 8 = 3।
সাধারণভাবে, হিপসর্টের গড় কেস সময়ের জটিলতা হল:
ও ( n log2n )যেখানে ডট মানে গুণ এবং n হল N, তালিকায় মোট উপাদানের সংখ্যা (যেকোনও তালিকা)।
উল্লেখ্য যে প্রথম উপাদান নিষ্কাশন অপারেশন উপেক্ষা করা হয়েছে. সময়ের জটিলতার বিষয়ে, তুলনামূলকভাবে কম সময় লাগে এমন অপারেশনগুলিকে উপেক্ষা করা হয়।
C++ এ কোডিং
C++ এর অ্যালগরিদম লাইব্রেরিতে, একটি make_heap() ফাংশন আছে। সিনট্যাক্স হল:
টেমপ্লেট < ক্লাস এলোমেলো অ্যাক্সেস ইটারেটর, ক্লাস তুলনা করা >constexpr অকার্যকর make_heap ( RandomAccessIterator প্রথমে, RandomAccessIterator শেষ, Compare compare ) ;
এটি একটি ভেক্টরের প্রথম উপাদানের দিকে নির্দেশ করে ইটারেটরকে তার প্রথম আর্গুমেন্ট হিসেবে নেয় এবং তারপর ভেক্টরের শেষের বাইরে ইটারেটরকে তার শেষ যুক্তি হিসেবে নির্দেশ করে। পূর্ববর্তী সাজানো তালিকার জন্য, ন্যূনতম হিপ পেতে নিম্নলিখিত সিনট্যাক্স ব্যবহার করা হবে:
ভেক্টর < int > vtr = { 9 , 19 , 24 , 5 , 3 , এগারো , 14 , 22 , 7 , 6 , 17 , পনের } ;ভেক্টর < int > :: পুনরাবৃত্তিকারী iterB = vtr শুরু ( ) ;
ভেক্টর < int > :: পুনরাবৃত্তিকারী iterE = vtr শেষ ( ) ;
make_heap ( iterB, iterE, বৃহত্তর < int > ( ) ) ;
এই কোডটি একটি ভেক্টর বিষয়বস্তুকে ন্যূনতম হিপ কনফিগারেশনে পরিবর্তন করে। নিম্নলিখিত C++ ভেক্টরগুলিতে, দুটি অ্যারের পরিবর্তে দুটি ভেক্টর ব্যবহার করা হবে।
একটি ভেক্টরের প্রথম উপাদানটি অনুলিপি করতে এবং ফেরত দিতে, ভেক্টর সিনট্যাক্স ব্যবহার করুন:
constexpr রেফারেন্স সামনে ( ) ;একটি ভেক্টরের প্রথম উপাদানটি সরাতে এবং এটিকে ফেলে দিতে, ভেক্টর সিনট্যাক্স ব্যবহার করুন:
constexpr পুনরাবৃত্তিকারী মুছে ফেলা ( const_iterator অবস্থান )একটি ভেক্টরের পিছনে একটি উপাদান যুক্ত করতে (পরবর্তী উপাদান), ভেক্টর সিনট্যাক্স ব্যবহার করুন:
constexpr অকার্যকর ফেরত পাঠাও ( const টি এবং এক্স ) ;প্রোগ্রামের শুরু হল:
# অন্তর্ভুক্ত করুন# অন্তর্ভুক্ত <অ্যালগরিদম>
# অন্তর্ভুক্ত <ভেক্টর>
ব্যবহার নামস্থান std ;
অ্যালগরিদম এবং ভেক্টর লাইব্রেরি অন্তর্ভুক্ত করা হয়. প্রোগ্রামের পরবর্তীটি হল heapsort() ফাংশন, যা হল:
অকার্যকর heapsort ( ভেক্টর < int > এবং oldV, ভেক্টর < int > এবং নতুন ভি ) {যদি ( oldV. আকার ( ) > 0 ) {
ভেক্টর < int > :: পুনরাবৃত্তিকারী iterB = oldV. শুরু ( ) ;
ভেক্টর < int > :: পুনরাবৃত্তিকারী iterE = oldV. শেষ ( ) ;
make_heap ( iterB, iterE, বৃহত্তর < int > ( ) ) ;
int পরবর্তী = oldV. সামনে ( ) ;
oldV. মুছে ফেলা ( iterB ) ;
নতুন ভি ফেরত পাঠাও ( পরবর্তী ) ;
heapsort ( পুরাতন ভি, নতুন ভি ) ;
}
}
এটি একটি পুনরাবৃত্ত ফাংশন। এটি C++ অ্যালগরিদম লাইব্রেরির make_heap() ফাংশন ব্যবহার করে। ফাংশনের সংজ্ঞার দ্বিতীয় কোড সেগমেন্টটি হিপ বিল্ডিংয়ের পরে পুরানো ভেক্টর থেকে প্রথম উপাদানটি বের করে এবং নতুন ভেক্টরের জন্য পরবর্তী উপাদান হিসাবে যোগ করে। লক্ষ্য করুন যে ফাংশনের সংজ্ঞায়, ভেক্টর পরামিতিগুলি হল রেফারেন্স, যখন ফাংশনটিকে সনাক্তকারী (নাম) দিয়ে বলা হয়।
এর জন্য একটি উপযুক্ত C++ প্রধান ফাংশন হল:
int প্রধান ( int argc, চর ** argv ){
ভেক্টর < int > oldV = { 9 , 19 , 24 , 5 , 3 , এগারো , 14 , 22 , 7 , 6 , 17 , পনের } ;
ভেক্টর < int > নতুন ভি ;
heapsort ( পুরাতন ভি, নতুন ভি ) ;
জন্য ( int i = 0 ; i < নতুন ভি আকার ( ) ; i ++ ) {
cout << নতুন ভি [ i ] << ' ;
}
cout << endl ;
ফিরে 0 ;
}
আউটপুট হল:
3 5 6 7 9 এগারো 14 পনের 17 19 22 24সাজানো (সম্পূর্ণভাবে)।
উপসংহার
নিবন্ধটি একটি সাজানোর অ্যালগরিদম হিসাবে সাধারণত Heapsort নামে পরিচিত Heap Sort এর প্রকৃতি এবং কার্যকারিতা সম্পর্কে বিস্তারিত আলোচনা করেছে। Heapify সময় জটিলতা, Heapsort চিত্রণ, এবং Heapsort একটি অ্যালগরিদম হিসাবে কভার এবং উদাহরণ দ্বারা সমর্থিত ছিল। একটি ভাল-লিখিত হিপসর্ট প্রোগ্রামের গড় সময় জটিলতা হল O(nlog(n))