سلام
سوال من در خصوص تیپ سوالات ادغام هست.
ارشد۹۳ یک هرم بیشینه m و یک هرم کمینه n تایی داریم می خواهیم ادغام کنیم و یک هرم بیشینه بسازیم
جواب پارسه : O(n+M) کافی است همه پشت سر هم قرار گرفته در جا دوباره هیپ شوند.
مدرسان شریف : اگر بخواهیم دو مین هیپ به تعداد mو n را با هم ادغام کنیم پیچیدگی زمای چقدر است ؟
چواب: گره ریشه درخت Heapبا mگره را در زمان logmحذف کرده و در زمان log nدر درخت Heapدومی درج می کنیم .
mlog m+ mlog n =m(log m + log n) = m log m.n
با این احوالات بنده به تناقض رسیدم !
جواب سوال مدرسان شریف را اگر از راه ساده پارسه برویم باید جواب خطی باشد . نه؟