مرتب‌سازی هرمی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
اصلاح جعبه اطلاعات، به‌دلیل به‌روزرسانی الگو:جعبه اطلاعات الگوریتم |
جز ابرابزار |
||
خط ۱۱:
'''مرتب‌سازی هرمی''' {{به انگلیسی|Heapsort}}، نوعی [[الگوریتم]] است که در آن از مقایسه برای چینش یک [[آرایه (رایانه)|آرایه]] یا فهرست استفاده می‌شود. این الگوریتم بخشی از خانوادهٔ [[مرتب‌سازی انتخابی]] است. با وجود اینکه در اکثر رایانه‌ها از الگوریتم [[مرتب‌سازی سریع|چینش سریع]] کند تر است ولی در بدترین حالت سرعت بالاتری (<math>O(n\log n)</math>) را دارا می‌باشد. این الگوریتم [[در-محل|در محل]] است، ولی حالت [[الگوریتم پایدار|پایداری]] ندارد.
در این
یکی از روش‌های مرتب‌سازی
بر اساس تعریف درخت heap، در یک max-heap یا min-heap بزرگترین یا کوچکترین مقدار بین داده‌ها همواره در ریشه درخت قرار دارد. یافتن بزرگترین یا کوچکترین عنصر بین عناصر، هزینه ثابت (Ө(
به عنوان مثال، min-heap زیر راتوضیح می‌دهیم:
خط ۴۸:
[[پرونده:11dheap.PNG]]
خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. خانه شماره
[[پرونده:12dheap.PNG]]
توجه = در حال حاضر درخت از پنج عنصر تشکیل شده‌است و عنصر ششم آرایه از عناصر درخت نیست. به همین ترتیب با حذف مجدد گره ریشه با مقدار
[[پرونده:12dheap.PNG]]
خط ۹۸:
</source>
== شبه کد
دو نوع Heap دودویی وجود دارد:max-Heapها وmin-Heapها. در هر دو نوع، مقادیر درون گره‌ها ویژگی Heap را ارضاء می‌کنند که ویژگی‌های هرکدام به نوع Heap بستگی دارند. ویژگیmax-Heap این است که برای هر گره i به جزء ریشه:
<source lang="java">
خط ۱۰۸:
return i/2
</source>
به عبارت دیگر مقدار یک گره حداکثر برابر مقدار پدرش است؛ بنابراین بزرگترین عضو max-Heap در ریشه ذخیره می‌شود. ویژگی min-Heap به صورت بر عکس شکل می‌گیرد. کوچکترین عضو در ریشه قرار می‌گیرد. در این الگوریتم
<source lang="java">
HEAPSORT(A)
خط ۱۲۸:
درخت min-heap مثال فوق را در نظر بگیرید. با حذف عدد یک به عنوان گره ریشه درخت و اعمال تغییرات لازم به نتیجه زیر می‌رسیم:
خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. خانه شماره
توجه داشته باشید که در حال حاضر درخت از پنج عنصر تشکیل شده‌است و عنصر ششم آرایه از عناصر درخت نیست. به همین ترتیب با حذف مجدد گره ریشه با مقدار
و با درج عنصر حذف شده در محل بلا استفاده:
خط ۱۳۹:
فهرست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:
در مرحله اول، کل فهرست از ابتدا تا انتها بررسی شده، و بزرگترین عنصر با عنصر انتهای فهرست نامرتب جابجا می‌شود:
در مرحله دوم، پیمایش از ابتدای فهرست تا عنصر چهارم صورت گرفته، و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود:
علت این که چرا عنصر پنجم بررسی نمی‌شود کاملا مشخص است. این عنصر در مرحله قبل به عنوان بزرگترین عنصر به انتهای فهرست منتقل شده‌است، و به طور حتم نیاز به جابجایی ندارد.
در مرحله سوم، عناصر اول تا سوم بررسی شده و بزرگترین عنصر به انتهای آن منتقل می‌شود:
و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:
و به این ترتیب فهرست مرتب می‌شود.
| |||