الگوریتم مرتب سازی هرمی (Heap Sort)

heap sort algorithm 7330 تصویر

الگوریتم مرتب سازی هرمی (Heap Sort)

الگوریتم مرتب سازی هرمی (Heap Sort)، یک تکنیک مرتب سازی بر اساس مقایسه مبتنی بر ساختار داده دودویی هیپ است. Heap Sort شبیه به الگوریتم مرتب سازی انتخابی است. در این الگوریتم ابتدا بزرگترین عنصر پیدا شده و در انتهای آرایه قرار می گیرد. همین روند برای باقی عناصر تکرار می شود تا آرایه به طور کامل مرتب شود.

heap sort algorithm 7330 1 تصویر

باینری هیپ چیست؟

اجازه دهید اول درخت دودویی کامل (Complete Binary Tree) را تعریف کنیم. Complete Binary Tree یک درخت دودویی است که در آن همه گره ها به جز برگ ها دارای دو فرزند هستند. یک باینری هیپ، یک درخت دودویی کامل است که در آن آیتم ها با ترتیب خاصی ذخیره می شوند. به طوری که مقدار گره والد بیشتر (یا کمتر) از مقادیر موجود در گره فرزندان است. یک هیپ را می توان با استفاده از درخت دودویی یا آرایه نمایش داد.

نحوه ساخت Heap

روش هیپ سازی (Heapify) فقط می تواند بر روی گره ای اعمال شود که فرزندان آن Heapify شده باشند. بنابراین عملیات heapification باید از پایین به بالا انجام شود.

برای درک بهتر نمونه زیر را مشاهده کنید:

پیاده سازی الگوریتم مرتب سازی هرمی (Heap Sort) به زبان سی پلاس پلاس:

امتحان کنید

خروجی:

نکات

ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است