رایانه

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

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

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

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

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

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

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

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

همانطور که مشاهده می کنید با n بار (n تعداد عناصر) حذف گره از درخت هیپ عناصر به صورت مرتب شده به دست می آیند. قبلا بحث کردیم که حذف گره از درخت heap از مرتبه ( O ( log₂n است. در نتیجه هزینه مرتب سازی آرایه n عنصری با روش مرتب سازی هرمی ( O ( n log₂n خواهد بود.

روش فوق یک مشکل کوچک دارد که بهتر است برطرف شود: ما به فضای اضافی برای مرتب سازی نیازمندیم. به عبارت دیگر برای مرتب کردن n عنصر، دو آرایه n عنصری نیاز داریم که یکی عناصر را به فرم درخت heap و دیگری عناصر مرتب شده را نگه می دارند. برای حل این مشکل کافی است دو آرایه مذکور را با هم به صورت ترکیبی در یک آرایه ذخیره کنیم! اما چگونه؟

درخت min-heap زیر را در نظر بگیرید:

با حذف ریشه درخت و اعمال تغییرات لازم به نتیجه زیر می رسیم:

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

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

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

و به همین ترتیب با حذف ریشه ها و درج آنها در محل های بلا استفاده به وجود آمده به نتیجه زیر خواهیم رسید:

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

بر اساس توضیحات فوق تابع مرتب سازی هرمی به زبان ++C به این صورت خواهد بود:

void heapsort ( int array [ ], int n )

{

int m = 0;

while ( m < n )

push ( array, m, array [ m + 1 ] );

while ( m )

array [ m + 1 ] = pop ( array, m );

}

در بررسی این کد به دو نکته توجه کنید:

1- توابع pop و push قبلا در مباحث معرفی درخت heap تعریف شده اند. در نتیجه در این قطعه کد فرض شده عناصر ما از اندیس 1 آرایه شروع شده اند. در صورت نیاز برای وارد کردن اندیس صفر یا باید کدها را کمی تغییر بدهید و یا اینکه بعد از مرتب کردن سایر عناصر موجود در اندیس 1 تا n - 1، عنصر اندیس صفر را هم در محل مناسبی از آرایه مرتب شده درج کنید.

۲- سه خط اول برای ساختن درخت heap و دو خط بعدی برای استخراج داده های مرتب از آن هستند.