دوستان لطفا راهنمایی کنید
ولی برای گزینه ها چه نمونه ای می شه آورد
جواب پوران: گزینه ۴
برای گزینه ۱ ساخت AVL رو داریم.
برای گزینه ۲ و ۳ ساخت ماکس هیپ رو داریم.
Sent from my GT-S5660 using Tapatalk 2
اشکالم این بود که فکر می کردم ساخت هیپ زمان n logn داره
سپاس
فکرمیکنم میشه هیپ رو طوری ساخت که nlogn باشه ولی خب ساخت با همون n بهتره.
Sent from my GT-S5660 using Tapatalk 2
(۲۶ دى ۱۳۹۲ ۱۲:۳۹ ب.ظ)Arshad93 نوشته شده توسط: فکرمیکنم میشه هیپ رو طوری ساخت که nlogn باشه ولی خب ساخت با همون n بهتره.ببخشید میشه بگید چطور میشه با n ساخت؟ممنون
Sent from my GT-S5660 using Tapatalk 2
راستش اثباتش طولانیه و تو کتاب قدسی توضیح کاملش هست.
من دراین حد میتونم توضیح بدم که تو روشی که هزینه اش nlogn بود یکی یکی عناصر آرایه در درخت درج میشد و بعد از هر درج درخت با logn مرتب میشد. اینجا همه عناصر آرایه رو سطح به سطح تو گره های درخت قرار داده و بعدا از پایین به بالا مرتب کرده. که در نهایت n بدست میاد. تو پوران هم یه توضیحاتی داده. ولی اثبات کاملش رو من توی کتاب قدسی دیدم.
Sent from my GT-S5660 using Tapatalk 2