برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: برای مرتب‌کردن عناصر با استفاده از درخت heap، نیاز به n عمل حذف گره ریشه از درخت دارد. عمل حذف گره ریشه در درخت heap خود از مرتبه (θ (log n است. در نتیجه کل این عملیات از مرتبه (θ (n log n خواهد بود. نکته قابل‌توجه دیگر، ساخت درخت heap از عناصر مورد نظر برای مرتب‌سازی است. در حالت عادی عناصر به صورت نامرتب و با چیدمان تصادفی در اختیار هر الگوریتم مرتب‌سازی قرار می‌گیرند. در این حالت یک هزینه زمانی دیگر برای ساخت درخت heap از روی چنین فهرستی مورد نیاز است. در روش بحث شده برای مرتب کردن n عنصر، دو آرایه n عنصری نیاز است. یکی از این آرایه‌ها عناصر را به فرم درخت heap به عنوان ورودی الگوریتم، و دیگری عناصر مرتب شده را به عنوان خروجی الگوریتم شامل می‌شوند. در چنین حالتی این الگوریتم یک روش مرتب‌سازی درجا نیست. با اندکی تغییر در روش پیاده‌سازی الگوریتم می‌توان عملکرد دو آرایه را در یک آرایه ادغام کرده، و میزان حافظه مصرفی را کاهش داد. درخت min-heap مثال فوق را در نظر بگیرید. با حذف عدد یک به عنوان گره ریشه درخت و اعمال تغییرات لازم به نتیجه زیر می‌رسیم: خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. خانه شماره ۶ حاوی اطلاعات بلا استفاده‌است. پس می‌توانیم عنصر حذف‌شده را در آن قرار دهیم: توجه = در حال حاضر درخت از پنج عنصر تشکیل شده‌است و عنصر ششم آرایه از عناصر درخت نیست. به همین ترتیب با حذف مجدد گره ریشه با مقدار ۴ آرایه زیر حاصل می‌شود: و با درج عنصر حذف‌شده در محل بلا استفاده: به همین ترتیب با تکرار الگوریتم نتیجه نهایی حاصل می‌شود: باید توجه داشت که بر خلاف نتیجه نهایی روش قبل، در این حالت عناصر به صورت نزولی به دست آمده‌اند. یعنی در این روش از درخت min-heap برای مرتب‌سازی نزولی و از درخت max-heap برای مرتب‌سازی صعودی استفاده می‌شود. می‌توانیم برای تبدیل آرایه [a [۱.. n به یک max-heap که [n=length [a از روال max-heapify به روش پایین به بالا استفاده کنیم. از آنجایی که عناصر زیر آرایه [a [(n / ۲) + ۱) …n همگی برگ‌های درخت هستند و بنابراین هر کدام‌یک heap یک عنصری برای شروع است، روالbuild-max-heap در راستای گره‌های باقی‌مانده درخت حرکت کرده و برای هر یک max-heapify را اجرا می‌کند. max-heapify یک زیرروال مهم برای دستکاری max-heapها است. ورودی آن آرایهa و اندیس i در …
برداشت:
مرتب‌سازی هرمی (به انگلیسی : heapsort) ، نوعی الگوریتم است که در آن از مقایسه برای چینش یک آرایه یا فهرست استفاده می‌شود . این الگوریتم بخشی از خانوادهٔ مرتب‌سازی انتخابی است . با وجود اینکه در اکثر رایانه‌ها از الگوریتم چینش سریع کندتر است ولی در بدترین حالت سرعت بالاتر () را دارا می‌باشد . این الگوریتم در محل است ، ولی حالت پایداری ندارد . در این مرتب‌سازی ، ابتدا از کل آرایه داده شده یک درخت مکس هیپ (یا درخت مین هیپ) می‌سازد . سپس بزرگترین مقدار را برمی‌دارد و در انتهای آرایه مرتب شده قرار می‌دهد . بعد از حذف بزرگترین مقدار ، دوباره از بقیه اعداد یک درخت مکس هیپ می‌سازد تا دومین عدد بزرگ یافت شود .