ورود / ثبت نام
در این آموزش با درخت max heap آشنا می‌شویم. ابتدا تابع مهم max_heapify مطرح می‌شود و در ادامه با کد این دستورات آشنا می‌شویم.
1- ساخت درخت max heap
2- اضافه کردن یک عنصر به max heap
3- حذف بزرگترین عدد از max heap
سپس با دو کاربر درخت max heap آشنا می‌شویم: مرتب سازی اعداد و ادغام k آرایه مرتب در یکدیگر. در مساله اول الگوریتمی با درجه n log(n) مطرح می‌شود و در مساله دوم سه الگوریتم بیان می‌شود که سریعترین الگوریتم از درجه nlog(k) است.
نکات و تمرینات این آموزش هم در انتهای این نوشته می‌توانید دنبال کنید.
نکات تکمیلی و تمرین های جلسه دهم ساختمان داده
1- درخت max_heap با n عنصر به صورت آرایه پیاده سازی شده است. الگوریتم پیدا کردن عنصر مینیمم در این درخت را بنویسید.
2- تابعی بنویسید که یک آرایه n تایی به عنوان پارامتر ورودی دریافت کند و تشخیص دهد که آیا آرایه max_heap است یا خیر
در آموزش ویدیویی بالا به این موضوع اشاره شد که دو نوع الگوریتم داریم، الگوریتمهای درجا و الگوریتمهای غیر درجا. الگوریتم مرتب سازی که در این آموزش مطرح شد به اشتباه الگوریتم غیردرجای مساله معرفی شد که لازم است این اشتباه را تصحیح کنیم. بد نیست تعریف الگوریتم درجا و غیر درجا را با هم مرور کنیم:
الگوریتمهای درجا الگوریتمهایی هستند که مصرف حافظه آنها متناسب با اندازه ورودی است. اگر ورودی از تتای n باشد (مثلا n عدد دریافت شود) مصرف حافطه الگوریتم هم باید از تتای n باشد. اگر مصرف حافظه الگوریتم مثلا از مرتبه تتای nlog(n) بود الگوریتم ما یک الگوریتم غیر درجاست