موضوع مقاله: مرتب‌سازی هرمی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی هرمی | مقدمه: مرتب‌سازی هرمی ، نوعی الگوریتم است که در آن از مقایسه برای چینش یک آرایه یا فهرست استفاده می‌شود. | ## بخش 1: مرتب‌سازی هرمی | با وجود اینکه در اکثر رایانه‌ها از الگوریتم چینش سریع کندتر است ولی در بدترین حالت سرعت بالاتر را دارا می‌باشد. در این مرتب‌سازی، ابتدا از کل آرایه داده شده یک درخت مکس هیپ (یا درخت مین هیپ) می‌سازد. بعد از حذف بزرگترین مقدار، دوباره از بقیه اعداد یک درخت مکس هیپ می‌سازد تا دومین عدد بزرگ یافت شود. بزرگ‌ترین مقدار در بین مقادیر باقی‌مانده را برمی‌دارد و آن را در مکان یکی قبل از انتهای آرایه قرار می‌دهد. این کار تا زمانی که هیچ مقداری در هرم باقی نماند و آرایه مرتب شده کامل شود، تکرار می‌شود. یکی از روش‌های مرتب‌سازی داده‌هااست، که براساس خصوصیات درخت heap پیاده‌سازی شده‌است. با حذف این عنصر از درخت، بزرگترین یا کوچکترین عنصر بعدی مجدداً در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج آن‌ها در محل جدید، یک آرایه مرتب‌شده نزولی ویا صعودی به دست خواهد آمد. | ## بخش 2: مرتب‌سازی هرمی | بررسی پیچیدگی زمانی مرتب‌سازی هرمی برای مرتب‌کردن عناصر با استفاده از درخت heap، نیاز به n عمل حذف گره ریشه از درخت دارد. در حالت عادی عناصر به صورت نامرتب و با چیدمان تصادفی در اختیار هر الگوریتم مرتب‌سازی قرار می‌گیرند. در این حالت یک هزینه زمانی دیگر برای ساخت درخت heap از روی چنین فهرستی مورد نیاز است. بررسی فضای مصرفی مرتب‌سازی هرمی در روش بحث شده برای مرتب کردن n عنصر، دو آرایه n عنصری نیاز است. یکی از این آرایه‌ها عناصر را به فرم درخت heap به عنوان ورودی الگوریتم، و دیگری عناصر مرتب شده را به عنوان خروجی الگوریتم شامل می‌شوند. با اندکی تغییر در روش پیاده‌سازی الگوریتم می‌توان عملکرد دو آرایه را در یک آرایه ادغام کرده، و میزان حافظه مصرفی را کاهش داد. در هر دو نوع، مقادیر درون گره‌ها ویژگی Heap را ارضاء می‌کنند که ویژگی‌های هرکدام به نوع Heap بستگی دارند. بررسی فضای مصرفی مرتب‌سازی هرمی در روش بحث شده برای مرتب کردن n عنصر، دو آرایه n عنصری نیاز است. | ## بخش 3: مرتب‌سازی هرمی | یکی از این آرایه‌ها عناصر را به فرم درخت heap به عنوان ورودی الگوریتم، و دیگری عناصر مرتب شده را به عنوان خروجی الگوریتم شامل می‌شوند. با اندکی تغییر در روش پیاده‌سازی الگوریتم می‌توان عملکرد دو آرایه را در یک آرایه ادغام کرده، و میزان حافظه مصرفی را کاهش داد. با حذف عدد یک به عنوان گره ریشه درخت و اعمال تغییرات لازم به نتیجه زیر می‌رسیم: خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. پس می‌توانیم عنصر حذف شده را در آن قرار دهیم: توجه داشته باشید که در حال حاضر درخت از پنج عنصر تشکیل شده‌است و عنصر ششم آرایه از عناصر درخت نیست. به همین ترتیب با حذف مجدد گره ریشه با مقدار ۴ آرایه زیر حاصل می‌شود: و با درج عنصر حذف شده در محل بلا استفاده: به همین ترتیب با تکرار الگوریتم نتیجه نهایی حاصل می‌شود: روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده، و به انتهای فهرست منتقل می‌کند. فهرست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود: ۲ ۸ ۴ ۱ ۷ در مرحله اول، کل فهرست از ابتدا تا انتها بررسی شده، و بزرگترین عنصر با عنصر انتهای فهرست نامرتب جابجا می‌شود: ۱) ۲ ۸ ۴ ۱ ۷ -> ۲ ۷ ۴ ۱ ۸ در مرحله دوم، پیمایش از ابتدای فهرست تا عنصر چهارم صورت گرفته، و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود: ۲) ۲ ۷ ۴ ۱ ۸ -> ۲ ۱ ۴ ۷ ۸ علت این که چرا عنصر پنجم بررسی نمی‌شود کاملاً مشخص است. این عنصر در مرحله قبل به عنوان بزرگترین عنصر به انتهای فهرست منتقل شده‌است، و به‌طور حتم نیاز به جابجایی ندارد. | ## جمع‌بندی | در مرحله سوم، عناصر اول تا سوم بررسی شده و بزرگترین عنصر به انتهای آن منتقل می‌شود: ۳) ۲ ۱ ۴ ۷ ۸ -> ۲ ۱ ۴ ۷ ۸ و در مرحله آخر دو عنصر باقی‌مانده مقایسه می‌شوند: ۴) ۲ ۱ ۴ ۷ ۸ -> ۱ ۲ ۴ ۷ ۸ و به این ترتیب فهرست مرتب می‌شود.