تالار گفتمان مانشت

دوستان لطفا راهنمایی کنید

ولی برای گزینه ها چه نمونه ای می شه آورد


جواب پوران: گزینه 4

برای گزینه 1 ساخت AVL رو داریم.
برای گزینه 2 و 3 ساخت ماکس هیپ رو داریم.

Sent from my GT-S5660 using Tapatalk 2

اشکالم این بود که فکر می کردم ساخت هیپ زمان n logn داره
سپاس

فکرمیکنم میشه هیپ رو طوری ساخت که nlogn باشه ولی خب ساخت با همون n بهتره.

Sent from my GT-S5660 using Tapatalk 2

(26 دى 1392 12:39 ب.ظ)Arshad93 نوشته شده توسط: [ -> ]فکرمیکنم میشه هیپ رو طوری ساخت که nlogn باشه ولی خب ساخت با همون n بهتره.

Sent from my GT-S5660 using Tapatalk 2

ببخشید میشه بگید چطور میشه با n ساخت؟ممنون

راستش اثباتش طولانیه و تو کتاب قدسی توضیح کاملش هست.
من دراین حد میتونم توضیح بدم که تو روشی که هزینه اش nlogn بود یکی یکی عناصر آرایه در درخت درج میشد و بعد از هر درج درخت با logn مرتب میشد. اینجا همه عناصر آرایه رو سطح به سطح تو گره های درخت قرار داده و بعدا از پایین به بالا مرتب کرده. که در نهایت n بدست میاد. تو پوران هم یه توضیحاتی داده. ولی اثبات کاملش رو من توی کتاب قدسی دیدم.

Sent from my GT-S5660 using Tapatalk 2