انجمنصفحه اولجستجوی انجمن

[ف.ش]

با دلیل صحبت کنید عقیده دارم که نشد حرف!!

[۱qazxsw2]

یکی بگه اشکالم چیه:
گره i‌ام رو با گره آخر جابجا میکنیم بعد (heapify(i
پلیز
؟؟؟؟؟؟؟؟؟؟

[ف.ش]

نه این که ۲ تا رو جابه جا کنیم بعد heapify کنیم که میرن سر جای اولشون!!!!

[مورتن]

حذف log n و مرتب سازی و ساخت heap از nlog n‌:
nlog n + log n = n log n

درضمن منو دعوا هم نکنید.

[۱qazxsw2]

مرسی
منظورم اینه که گره i به آخر آرایه منتقل بشه و به جاش گره آخر به خانه iام بعدش ..........
دقیقا مثل حذف از اول آرایه

[ف.ش]

هیپ رو که داشتیم دیگه چرا بسازیم!!
گفتم با دلیل صحبت کنید دعوا ندارم که!

[مورتن]

داشتیم دیگه نداریم. درخت داریم فقط . پس دوباره هیپ باید ساخته بشود.

[shaghayegh]

بالاخره جواب چی شد؟
منم nlog زدم

[alavinejad]

به نظر من چون گفته بود عنصر i‌ام ارایه، با زمان یک میشه دسترسی داشت بهش و حذفش می کنیم بعد عنصر اخر می زاریم جای اون و heapify رو اجرا می کنیم که میشه logn

[۱qazxsw2]

(۲۹ بهمن ۱۳۸۹ ۰۴:۱۶ ب.ظ)alavinejad نوشته شده توسط:  به نظر من چون گفته بود عنصر i‌ام ارایه، با زمان یک میشه دسترسی داشت بهش و حذفش می کنیم بعد عنصر اخر می زاریم جای اون و heapify رو اجرا می کنیم که میشه logn

دقیقا موافقم منم همینو میگم دیگه کسی در کم نمیکنه

[Maryam-X]

alavinejad جان:
یه سوال:شما عنصر i‌ام هیپ رو از کجا تشخیص می دی؟(عنصر ا‌ام هیپ را خواسته بود نه آرایه‌ی مرتب)
به نظرم فقط اولین عنصر هیپ(ماکس)پیداست و آخرین عنصر هم فقط می دونیم توی برگ هاست.
بقیه رو هم می دونیم بین سطح ۲ تا i قرار گرفتند ولی دقیق جاشون رو نمی دونیم.


بچه‌ها این مسئله از راه های متفاوت حل میشه با جواب های متفاوت
زیاد بهش گیر ندید
صد در صد بستگی داره به اینکه منظور خود طراح سوال چی بوده.

[sjj]

منم اونو LogN زدم با استدلال alavinejad جان

[mmpf]

اون سوال رو منم logn زدم.چون فقط ریشه رو حذف میکنیم تو heap .پس حذف (۱)O وبعد از اون هم با logn مرتب میکنیم که heap باقی بمونه.وکلش میشه (logn) .ونیازی به ساخت دوباره نیست.
اون تعداد ضرب‌ها رو چند زدید؟من (۴t(n^2رو زدم. اون سوال که گفته بود مرتب سازی تو ۰ تا n^2 از مرتبه چند میشه رو چند زدید؟؟ 

[sal_dovomi]

یه جوری تحلیل کنید که در آخر بهlgn برسید.والابد حال گیری میشه

[bijibuji]

(۲۹ بهمن ۱۳۸۹ ۰۴:۱۶ ب.ظ)alavinejad نوشته شده توسط:  به نظر من چون گفته بود عنصر i‌ام ارایه، با زمان یک میشه دسترسی داشت بهش و حذفش می کنیم بعد عنصر اخر می زاریم جای اون و heapify رو اجرا می کنیم که میشه logn

دقیقا همینه

(۲۹ بهمن ۱۳۸۹ ۰۴:۲۴ ب.ظ)Maryam-X نوشته شده توسط:  alavinejad جان:
یه سوال:شما عنصر i‌ام هیپ رو از کجا تشخیص می دی؟(عنصر ا‌ام هیپ را خواسته بود نه آرایه‌ی مرتب)
به نظرم فقط اولین عنصر هیپ(ماکس)پیداست و آخرین عنصر هم فقط می دونیم توی برگ هاست.
بقیه رو هم می دونیم بین سطح ۲ تا i قرار گرفتند ولی دقیق جاشون رو نمی دونیم.


بچه‌ها این مسئله از راه های متفاوت حل میشه با جواب های متفاوت
زیاد بهش گیر ندید
صد در صد بستگی داره به اینکه منظور خود طراح سوال چی بوده.

عنصر iام هیپ‌، همون عنصر i‌ام آرایه است. درسته که بین همزاد‌ها ترتیبی نیست. اما مقصود از عنصر i‌ام هیپ، i امین بزرگترین (در MaxHeap) عنصر نیست. بلکه i امین عضو هست که در مکان i‌ام آرایه است.
با ۱ بار (مرتبه ۱) عنصر i‌ام رو پیدا می کنیم.
با ۱ بار اون رو حذف می کنیم و عنصر n‌ام رو جایگزین می کنیم.
با log(n بار این عنصر رو با فرزندانش جابجا می کنیم تا هیپ بشه

(۲۹ بهمن ۱۳۸۹ ۰۵:۵۲ ب.ظ)mmpf نوشته شده توسط:  اون سوال رو منم logn زدم.چون فقط ریشه رو حذف میکنیم تو heap .پس حذف (۱)O وبعد از اون هم با logn مرتب میکنیم که heap باقی بمونه.وکلش میشه (logn) .ونیازی به ساخت دوباره نیست.

پاسخ تون درسته، اما ریشه نباید حذف بشه، بلکه عنصر i‌ام باید حذف بشه. شانس آوردی کنکور تشریحی نیست‌ها

نقل قول: اون تعداد ضرب‌ها رو چند زدید؟من (۴t(n^2رو زدم. اون سوال که گفته بود مرتب سازی تو ۰ تا n^2 از مرتبه چند میشه رو چند زدید؟؟ 

این سوال رو من گزینه O(n زدم چون از رادیکس می شه استفاده کرد. radix sort که مرتبه اش دراین مورد n هست. این سوال سال ۸۸ آی تی اومده بود