مرتب‌سازی هرمی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ←جایگزینی با [[وپ:اشتباه|اشتباهیاب]]: حدف⟸حذف، هییپ⟸هیپ، |
FreshmanBot (بحث | مشارکت‌ها) جز اصلاح فاصله مجازی + اصلاح نویسه با استفاده از AWB |
||
خط ۱۱:
'''مرتب‌سازی هرمی''' {{به انگلیسی|Heapsort}}، نوعی [[الگوریتم]] است که در آن از مقایسه برای چینش یک [[آرایه (رایانه)|آرایه]] یا فهرست استفاده می‌شود. این الگوریتم بخشی از خانوادهٔ [[مرتب‌سازی انتخابی]] است. با وجود اینکه در اکثر رایانه‌ها از الگوریتم [[مرتب‌سازی سریع|چینش سریع]] کندتر است ولی در بدترین حالت سرعت بالاتری (<math>O(n\log n)</math>) را دارا می‌باشد. این الگوریتم [[در-محل|در محل]] است، ولی حالت [[الگوریتم پایدار|پایداری]] ندارد.
در این مرتب‌سازی، ابتدا از کل آرایه داده شده یک [[درخت مکس هیپ]] (یا [[درخت مین هیپ]]) می‌سازد. سپس بزرگترین مقدار را برمی‌دارد و در انتهای آرایه مرتب شده قرار می‌دهد. بعد از حذف بزرگترین مقدار، دوباره از بقیه اعداد یک درخت مکس هیپ می‌سازد تا دومین عدد بزرگ یافت شود. بزرگترین مقدار در بین مقادیر
یکی از روش‌های مرتب‌سازی داده‌هااست، که براساس خصوصیات درخت heap پیاده‌سازی شده‌است.
بر اساس تعریف درخت heap، در یک max-heap یا min-heap بزرگترین یا کوچکترین مقدار بین داده‌ها همواره در ریشه درخت قرار دارد. یافتن بزرگترین یا کوچکترین عنصر بین عناصر، هزینه ثابت (Ө(۱ دارد. با حذف این عنصر از درخت، بزرگترین یا کوچکترین عنصر بعدی مجدداً در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج
به عنوان مثال، min-heap زیر راتوضیح می‌دهیم:
خط ۷۱:
== ساختن یک درخت Max-Heap ==
می‌توانیم برای تبدیل آرایه[A[1..n به یک max-Heap که [n=length[A از روال [[MAX-HEAPIFY]] به روش پایین به بالا استفاده کنیم. از آنجایی که عناصر زیر آرایه [A[(n/2)+1)...n همگی برگ‌های درخت هستند و بنابراین هر کدام یک Heap یک عنصری برای شروع است، روالBUILD-MAX-HEAP در راستای گره‌های
<source lang="java">
خط ۱۰۱:
A[PARENT(i)]>A[i]
</source>
<source lang="java">
PARENT(i)
خط ۱۴۶:
۲) ۲ ۷ ۴ ۱ ۸ -> ۲ ۱ ۴ ۷ ۸
علت این که چرا عنصر پنجم بررسی نمی‌شود کاملاً مشخص است. این عنصر در مرحله قبل به عنوان بزرگترین عنصر به انتهای فهرست منتقل شده‌است، و
در مرحله سوم، عناصر اول تا سوم بررسی شده و بزرگترین عنصر به انتهای آن منتقل می‌شود:
۳) ۲ ۱ ۴ ۷ ۸ -> ۲ ۱ ۴ ۷ ۸
و در مرحله آخر دو عنصر
۴) ۲ ۱ ۴ ۷ ۸ -> ۱ ۲ ۴ ۷ ۸
| |||