مرتب‌سازی هرمی: تفاوت میان نسخه‌ها

در این مرتب سازی، ابتدا از کل آرایه داده شده یک [[درخت مکس هیپ]] (یا [[درخت مین هیپ]]) می‌سازد. سپس بزرگترین مقدار را بر می‌دارد و در انتهای آرایه مرتب شده قرار می‌دهد. بعد از حدف بزرگترین مقدار، دوباره از بقیه اعداد یک درخت مکس هییپ می‌سازد تا دومین عدد بزرگ یافت شود. بزرگ‌ترین مقدار در بین مقادیر باقی مانده را برمی دارد و آن را در مکان یکی قبل از انتهای آرایه قرار می‌دهد. این کار تا زمانی که هیچ مقداری در هرم باقی نماند و آرایه مرتب شده کامل شود، تکرار می‌شود.

 

 

یکی از روش‌های مرتب‌سازی داده‌هااست,که براساس خصوصیات درخت heap پیاده‌سازی شده‌است.

به عنوان مثال، min-heap زیر راتوضیح می‌دهیم:

 

 

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

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

 

 

 

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