مرتبسازی هرمی: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
جز ربات: حذف میانویکی موجود در ویکیداده: ۲۶ میانویکی |
جزبدون خلاصۀ ویرایش |
||
خط ۱:
'''مرتبسازی هرمی''' {{به انگلیسی|Heapsort}}، نوعی [[الگوریتم]] است که در آن از مقایسه برای چینش یک [[آرایه (رایانه)|آرایه]] یا فهرست استفاده میشود. این الگوریتم بخشی از خانوادهٔ [[مرتبسازی انتخابی]] است. با وجود اینکه در اکثر رایانهها از الگوریتم [[مرتبسازی سریع|چینش سریع]] کند تر است ولی در بدترین حالت سرعت بالاتری (<math>O(n log n)</math>) را دارا میباشد. این الگوریتم [[در-محل|در محل]] است، ولی حالت [[الگوریتم پایدار|پایداری]] ندارد.
در این مرتب سازی، ابتدا از کل آرایه داده شده یک [[درخت مکس هیپ]] (یا [[درخت مین هیپ]]) میسازد. سپس بزرگترین مقدار را بر میدارد و در انتهای آرایه مرتب شده قرار میدهد. بعد از حدف بزرگترین مقدار، دوباره از بقیه اعداد یک درخت مکس هییپ میسازد تا دومین عدد بزرگ یافت شود. بزرگترین مقدار در بین مقادیر باقی مانده را برمی دارد و آن را در مکان یکی قبل از انتهای آرایه قرار میدهد. این کار تا زمانی که هیچ مقداری در هرم باقی نماند و آرایه مرتب شده کامل شود، تکرار میشود.
|