مرتب سازی هرمی تکرار شونده – به زبان ساده

۲۸۳ بازدید
آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲
زمان مطالعه: ۵ دقیقه
دانلود PDF مقاله
مرتب سازی هرمی تکرار شونده – به زبان سادهمرتب سازی هرمی تکرار شونده – به زبان ساده

در این مطلب، به «مرتب سازی هرمی تکرار شونده» (Iterative HeapSort) پرداخته‌ایم که در واقع همان الگوریتم مرتب سازی هرمی است که به روش تکرار شونده (Iterative) پیاده‌سازی شده است. همچنین، پیاده‌سازی الگوریتم مرتب سازی هرمی تکرار شونده در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «پایتون» (Python) پیاده‌سازی شده است. «مرتب‌سازی هرمی» (HeapSort) گونه‌ای از الگوریتم‌های مبتنی بر مقایسه است که طی آن، ابتدا درخت بیشینه ساخته می‌شود و سپس عنصر ریشه با آخرین عنصر (به تعداد اندازه) جایگزین می‌شود و مشخصات هرم را هر بار نگهداری می‌کند تا در نهایت آن را مرتب کند. مثال زیر برای درک بهتر این مفهوم بیان شده است.

997696
Input :  10 20 15 17 9 21
Output : 9 10 15 17 20 21 

Input:  12 11 13 5 6 7 15 5 19
Output: 5 5 6 7 11 12 13 15 19

در مثال اول، ابتدا باید هرم بیشینه ساخته شود. بنابراین، کار با عدد ۲۰ به عنوان فرزند آغاز می‌شود و والدین آن بررسی می‌شوند. در اینجا، ۱۰ کوچک‌تر است. بنابراین این دو با یکدیگر جا به جا می‌شوند. داریم: 20  10  15  17  9  2120\; 10\; 15\; 17\; 9\; 21. اکنون، فرزند ۱۷ بزرگ‌تر از والد خودش یعنی ۱۰ است. بنابراین، هر دو با هم جا به جا می‌شوند و ترتیب آن‌ها 20  17  15  10  9  2120\; 17\; 15\; 10\; 9\; 21 خواهد بود. اکنون، فرزند ۲۱ بزرگ‌تر از والد خود یعنی ۱۵ است. بنابراین، هر دو با یکدیگر جایگزین می‌شوند.

داریم: 20  17  21  10  9  1520\; 17\; 21\; 10\; 9\; 15. اکنون، ۲۱ بزرگ‌تر از والد خودش ۲۰ است. بنابراین: 21  17  20  10  9  1521\; 17\; 20\; 10\; 9\; 15. این «هرم بیشینه» (Max Heap) است. اکنون باید مرتب‌سازی اعمال شود. در اینجا باید اولین عنصر با آخرین عنصر جا به جا شود و در عین حال، خصوصیات هرم بیشینه نیز حفظ شود. بنابراین، بعد از اولین جا به جایی 15  17  20  10  9  2115\; 17\; 20\; 10\; 9\; 21 را داریم که این مورد، نقض خصوصیات هرم بیشینه است؛ بنابراین، باید آن را حفظ کرد. در نهایت، ترتیب به صورت زیر خواهد بود.

20 17 15 10 9 21
17 10 15 9 20 21
15 10 9 17 20 21
10 9 15 17 20 21
9 10 15 17 20 21

در اینجا، قسمت زیر خط‌دار، در واقع همان قسمت مرتب شده است.

مرتب سازی هرمی تکرار شونده در ++C

مرتب سازی هرمی تکرار شونده در جاوا

مرتب سازی هرمی تکرار شونده در پایتون ۳

خروجی قطعه کدهای بالا، به صورت زیر است.

Given array: 10 20 15 17 9 21 

Sorted array: 9 10 15 17 20 21

در اینجا، هر دو تابع buildMaxHeap و heapSort از درجه O(nlogn)‎ هستند.

بنابراین، پیچیدگی زمانی کلی برابر با (O(nlogn است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
دانلود PDF مقاله
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *