تالار گفتمان مانشت
تست ۵۷ طراحی الگوریتم آی تی سال ۸۴ - نسخه‌ی قابل چاپ

تست ۵۷ طراحی الگوریتم آی تی سال ۸۴ - rad.bahar - 16 بهمن ۱۳۹۰ ۰۵:۵۰ ب.ظ

می خواهیم دو هیپ منیمم با اندازه های mوn را در یک هیپ به اندازه n+m ادقام کنیم فرض کنید که هیپ خروجی به صورن درخت باشدبا فرص n>m چرا این کار را در logn می توان انجام داد

تست ۵۷ it84 - atharrashno - 20 بهمن ۱۳۹۰ ۰۹:۴۳ ب.ظ

ببین شما در بهترین حالت فرض کن دو تا هیپ پر داری میخوای به یک هیپ تبدیل کنی
اول یک گره خالی ایجاد میکنی بعد دو تا درخت را به چپ و راست درخت اضافه میکنی بعد بین اون دو تا ریشه دو تا درخت که الان فرزند چپ و راست گره خالی میشن کوچیکترین میفرستی بالا اونی که ریشه اش رفته بالا دوباره باید هیب بودنش برقرار بشه در بدترین حالت

به اندازه عمق درخت بیشتره یعنی ان باید حرکت کنیم که هیپ فای را انجام بدیم


اگه این کار با یک مثال انجام بدی متوجه میشی درخت حاصل نمیتونه خاصیت کامل بودن هیپ را داشته باشه پس ما میتونیم این کار را در زمان لگاریتم ان انجام بدیم اما درخت حاصل صرفا نمیتونه در به صورت ارایه نمایش داده بشه به خاطر همون عناصری که خالی می مونند