سلام


سوال من در خصوص تیپ سوالات ادغام هست.

ارشد۹۳ یک هرم بیشینه 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‬‬


با این احوالات بنده به تناقض رسیدم !
جواب سوال مدرسان شریف را اگر از راه ساده پارسه برویم باید جواب خطی باشد . نه؟