مرتب‌سازی هرمی

مرتب‌سازی هرمی (Heap Sort) یکی از روش‌های مشهور مرتب‌سازی داده‌ها است که بر اساس خصوصیات درخت heap (هیپ، هرم یا کپه)  و عملکرد آن پیاده‌سازی شده است.

بر اساس تعریف درخت heap، در یک max-heap (یا min-heap) بزرگترین (یا کوچکترین) مقدار بین داده‌ها همواره در ریشه‌ی درخت قرار دارد. یافتن بزرگترین (یا کوچکترین) عنصر بین عناصر، هزینه‌ی ثابت ( Ө( 1 دارد. با حذف این عنصر از درخت، بزرگترین (یا کوچکترین) عنصر بعدی مجددا در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج آنها در محل جدید، یک آرایه‌ی مرتب‌شده‌ی نزولی (یا صعودی) به دست خواهد آمد.

به عنوان نمونه، min-heap زیر را در نظر بگیرید:

مراحل مرتب‌سازی هرمی به ترتیب زیر خواهد بود:

Step 0 )   min-heap: 1, 4, 5, 8, 6, 9      -    list:

Step 1 )   min-heap: 4, 6, 5, 8, 9          -    list: 1

Step 2 )   min-heap: 5, 6, 9, 8              -    list: 1, 4

Step 3 )   min-heap: 6, 8, 9                  -    list: 1, 4, 5

Step 4 )   min-heap: 8, 9                      -    list: 1, 4, 5, 6

Step 5 )   min-heap: 9                          -    list: 1, 4, 5, 6, 8

Step 6 )   min-heap:                             -    list: 1, 4, 5, 6, 8, 9

در پایان، آرایه‌ی list شامل اطلاعات مرتب‌شده‌ی صعودی است.

بررسی پيچيدگي زمانی مرتب‌سازی هرمی

برای مرتب‌کردن عناصر با استفاده از درخت heap، نیاز به n عمل حذف گره ریشه از درخت (یا عمل pop) وجود دارد. عمل حذف گره ریشه در درخت heap خود از مرتبه‌ی ( Θ( log n است. در نتیجه کل این عملیات از مرتبه‌ی ( Θ( n log n خواهد بود.

نکته‌ی قابل توجه دیگر، ساخت درخت heap از عناصر مورد نظر برای مرتب‌سازی است. در حالت عادی عناصر به صورت نامرتب و با چیدمان تصادفی در اختیار هر الگوریتم مرتب‌سازی قرار می‌گیرند. در این حالت یک هزینه‌ی زمانی دیگر برای ساخت درخت heap از روی چنین لیستی مورد نیاز است.

بررسی فضای مصرفی مرتب‌سازی هرمی

در روش بحث شده برای مرتب کردن n عنصر، دو آرایه‌ی n عنصری نیاز است. یکی از این آرایه‌ها عناصر را به فرم درخت heap به عنوان ورودی الگوریتم و دیگری عناصر مرتب شده را به عنوان خروجی الگوریتم شامل می‌شوند. در چنین حالتی این الگوریتم یک روش مرتب‌سازی درجا نیست. با اندکی تغییر در روش پیاده‌سازی الگوریتم می‌توان عملکرد دو آرایه را در یک آرایه ادغام کرده و میزان حافظه‌ی مصرفی را کاهش داد.

درخت min-heap مثال فوق را در نظر بگیرید. با حذف عدد یک به عنوان گره ریشه درخت و اعمال تغییرات لازم به نتیجه‌ی زیر می‌رسیم:

خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. خانه‌ی شماره‌ی 6 حاوی اطلاعات سوخته و بلا استفاده است. پس می‌توانیم عنصر حذف شده را در آن قرار دهیم:

توجه داشته باشید که در حال حاضر درخت از پنج عنصر تشکیل شده است و عنصر ششم آرایه از عناصر درخت نیست. به همین ترتیب با حذف مجدد گره ریشه با مقدار 4 آرایه زیر حاصل می‌شود:

و با درج عنصر حذف شده در محل بلا استفاده:

به همین ترتیب با تکرار الگوریتم نتیجه‌ی نهایی حاصل می‌شود:

البته توجه داشته باشید که بر خلاف نتیجه‌ی نهایی روش قبل، در این حالت عناصر به صورت نزولی به دست آمده‌اند. یعنی در این روش از درخت min-heap برای مرتب‌سازی نزولی و از درخت max-heap برای مرتب‌سازی صعودی استفاده می‌شود.