جلسه دهم ساختمان داده، max heap

دسته‌بندی:
یک دیدگاه

در این آموزش با درخت max heap آشنا می‌شویم. ابتدا تابع مهم max_heapify مطرح می‌شود و در ادامه با کد این دستورات آشنا می‌شویم.

۱- ساخت درخت max heap
۲- اضافه کردن یک عنصر به max heap
۳- حذف بزرگترین عدد از max heap

سپس با دو کاربر درخت max heap آشنا می‌شویم: مرتب سازی اعداد و ادغام k آرایه مرتب در یکدیگر. در مساله اول الگوریتمی با درجه n log(n) مطرح می‌شود و در مساله دوم سه الگوریتم بیان می‌شود که سریعترین الگوریتم از درجه nlog(k) است.

نکات و تمرینات این آموزش هم در انتهای این نوشته می‌توانید دنبال کنید.

مشاهده این آموزش در آپارات

نکات تکمیلی و تمرین های جلسه دهم ساختمان داده

۱- درخت max_heap با n عنصر به صورت آرایه پیاده سازی شده است. الگوریتم پیدا کردن عنصر مینیمم در این درخت را بنویسید.

۲- تابعی بنویسید که یک آرایه n تایی به عنوان پارامتر ورودی دریافت کند و تشخیص دهد که آیا آرایه max_heap است یا خیر

در آموزش ویدیویی بالا به این موضوع اشاره شد که دو نوع الگوریتم داریم، الگوریتمهای درجا و الگوریتمهای غیر درجا. الگوریتم مرتب سازی که در این آموزش مطرح شد به اشتباه الگوریتم غیردرجای مساله معرفی شد که لازم است این اشتباه را تصحیح کنیم. بد نیست تعریف الگوریتم درجا و غیر درجا را با هم مرور کنیم:

الگوریتمهای درجا الگوریتمهایی هستند که مصرف حافظه آنها متناسب با اندازه ورودی است. اگر ورودی از تتای n باشد (مثلا n عدد دریافت شود) مصرف حافطه الگوریتم هم باید از تتای n باشد. اگر مصرف حافظه الگوریتم مثلا از مرتبه تتای nlog(n) بود الگوریتم ما یک الگوریتم غیر درجاست

  • نویسنده
    حمید جهانگیری
  • تعداد بازدید
    290
۱دیدگاه فرستاده شده است.
شما هم دیدگاه خود را بنویسید
نوشته‌های ویژه
اخبار ویژه

با عضویت در خبرنامه، تازه‌ترین نوشته‌های وبلاگ را در ایمیل‌تان دریافت کنید.
برای عضویت نشانی ایمیل خود را وارد کرده و بر روی دکمه عضویت کلیک نمایید.