۰
subtitle
ارسال: #۱
  
تست ۵۷ طراحی الگوریتم آی تی سال ۸۴
می خواهیم دو هیپ منیمم با اندازه های mوn را در یک هیپ به اندازه n+m ادقام کنیم فرض کنید که هیپ خروجی به صورن درخت باشدبا فرص n>m چرا این کار را در logn می توان انجام داد
۰
ارسال: #۲
  
تست ۵۷ it84
ببین شما در بهترین حالت فرض کن دو تا هیپ پر داری میخوای به یک هیپ تبدیل کنی
اول یک گره خالی ایجاد میکنی بعد دو تا درخت را به چپ و راست درخت اضافه میکنی بعد بین اون دو تا ریشه دو تا درخت که الان فرزند چپ و راست گره خالی میشن کوچیکترین میفرستی بالا اونی که ریشه اش رفته بالا دوباره باید هیب بودنش برقرار بشه در بدترین حالت
به اندازه عمق درخت بیشتره یعنی ان باید حرکت کنیم که هیپ فای را انجام بدیم
اگه این کار با یک مثال انجام بدی متوجه میشی درخت حاصل نمیتونه خاصیت کامل بودن هیپ را داشته باشه پس ما میتونیم این کار را در زمان لگاریتم ان انجام بدیم اما درخت حاصل صرفا نمیتونه در به صورت ارایه نمایش داده بشه به خاطر همون عناصری که خالی می مونند
اول یک گره خالی ایجاد میکنی بعد دو تا درخت را به چپ و راست درخت اضافه میکنی بعد بین اون دو تا ریشه دو تا درخت که الان فرزند چپ و راست گره خالی میشن کوچیکترین میفرستی بالا اونی که ریشه اش رفته بالا دوباره باید هیب بودنش برقرار بشه در بدترین حالت
به اندازه عمق درخت بیشتره یعنی ان باید حرکت کنیم که هیپ فای را انجام بدیم
اگه این کار با یک مثال انجام بدی متوجه میشی درخت حاصل نمیتونه خاصیت کامل بودن هیپ را داشته باشه پس ما میتونیم این کار را در زمان لگاریتم ان انجام بدیم اما درخت حاصل صرفا نمیتونه در به صورت ارایه نمایش داده بشه به خاطر همون عناصری که خالی می مونند
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close