حل سوال ۴۲
ببینید کافیه عنصر [tex]i[/tex]ام رو حذف کنیم و سپس اخرین عنصر ارایه رو جای این عنصر بذاریم(خب تا اینجا هر کاری کردیم از مزتبه زمانی [tex]\theta(1)[/tex] بودش).حالا ممکنه با این جا به جایی که انجام دادیم خاصیت MaxHeap ارایه رو از بین برده باشیم ،پس کافیه یه بار الگوریتم Heapify رو اجرا کنیم و بعد دوباره MaxHeap داریم.زمان اجرای الگوریتم Heapify هم [tex]\theta(Logn)[/tex] میشه.پس گزینه ۲ درسته
حل سوال ۳۷
قسمت اول میتونیم این کارو انجام بدیم:عنصر دلخواه رو حذف کنیم و اخرین عنصر رو بیاریم جایگزینش کنیم و Heapify رو انجام بدیم.مرتبه کل میشه [tex]Logn[/tex]
قسمت دوم میتونیم به عنوان اخرین عنصر ،عنصر دلخواهمون رو درج کنیم و بعدش الگوریتم Heapify رو اجرا کنیم.مرتبه کل میشه [tex]Logn[/tex]
قسمت سوم میتونیم مقدار عنصر مورد نظرمون رو کاهش بدیم . بعد الگوریتم Heapify رو اجرا کنیم.مرتبه کل میشه [tex]Logn[/tex]
پس گزینه ۴ درسته
(02 دى 1393 12:15 ق.ظ)miladcr7 نوشته شده توسط: [ -> ]حل سوال ۴۲
ببینید کافیه عنصر [tex]i[/tex]ام رو حذف کنیم و سپس اخرین عنصر ارایه رو جای این عنصر بذاریم(خب تا اینجا هر کاری کردیم از مزتبه زمانی [tex]\theta(1)[/tex] بودش).حالا ممکنه با این جا به جایی که انجام دادیم خاصیت MaxHeap ارایه رو از بین برده باشیم ،پس کافیه یه بار الگوریتم Heapify رو اجرا کنیم و بعد دوباره MaxHeap داریم.زمان اجرای الگوریتم Heapify هم [tex]\theta(Logn)[/tex] میشه.پس گزینه ۲ درسته
در هیپ حذف از ریشه صورت میگیره ریشه حذف بشه از مرتبه یک وبرسی هیپ بودن log n .ولی اگه عنصر مورد نظر ریشه نبود یه عنصر خاص بود چطو؟توهمین سوالم گفته iبین 1 وn چطور عنصر مورد نظر ریشه بگیرم شاید منظورش یه عنصر خاصه که دراین صورت فکر کنم n log n .
خیلی ممنون
(02 دى 1393 12:30 ق.ظ)mariy نوشته شده توسط: [ -> ] (02 دى 1393 12:15 ق.ظ)miladcr7 نوشته شده توسط: [ -> ]حل سوال ۴۲
ببینید کافیه عنصر [tex]i[/tex]ام رو حذف کنیم و سپس اخرین عنصر ارایه رو جای این عنصر بذاریم(خب تا اینجا هر کاری کردیم از مزتبه زمانی [tex]\theta(1)[/tex] بودش).حالا ممکنه با این جا به جایی که انجام دادیم خاصیت MaxHeap ارایه رو از بین برده باشیم ،پس کافیه یه بار الگوریتم Heapify رو اجرا کنیم و بعد دوباره MaxHeap داریم.زمان اجرای الگوریتم Heapify هم [tex]\theta(Logn)[/tex] میشه.پس گزینه ۲ درسته
در هیپ حذف از ریشه صورت میگیره ریشه حذف بشه از مرتبه یک وبرسی هیپ بودن log n .ولی اگه عنصر مورد نظر ریشه نبود یه عنصر خاص بود چطو؟توهمین سوالم گفته iبین ۱ وn چطور عنصر مورد نظر ریشه بگیرم شاید منظورش یه عنصر خاصه که دراین صورت فکر کنم n log n .
خیلی ممنون
ببینید نیازی نیست حتما حذف از ریشه صورت بگیره!!مثلا میگه میخوایم عنصر 5 رو حذف کنیم و ما هم از طریق اندیس بهش دسترسی پیدا میکنیم و این کار از مرتبه 1 هستش
سوال ۳۷ رو فکر کنم اشتباه متوجه شدید، درسته مرتبه هر سه عمل از Logn هست ولی این درخت که توی سوال گفته شده هیپ نیست!
یه درخت انتخابی مدنظر طراح بوده که برای حذف هم از مرتبه Log n هست البته وقتی مثلا عدد ۳ رو قرار حذف کنه و نمیدونم ایندکس اون چنده، با مرتبه log n محل عدد ۳ پیدا میشه و به نظرم برای حذف اگر آخرین عنصر برگ جایگزین عدد حذف شده کنیم و پس از اون با حداکثر مرتبه logn میشه درخت رو بازسازی کرد. شکل رو در ضمیمه آوردم.
در حالت خاص ممکنه که آوردن آخرین برگ بهینه نباشه و اگه اون برگ یه گره برادر داشته باشه، باید یه مقایسه انجام بدیم و بزرگتره رو بیاریم. شکل دوم که نیازی نباشه اون سمت رو هم بازسازی کنیم.
ببینید فک نکنم سوالو اشتباه فهمیده باشم.سوال گفته یه داده ساختار داریم که درخت دودویی کامل هستش.مگه هیپ درخت دودویی کامل نیستش؟؟؟خود سوال هم گفته مثل هیپ
در ضمن ببینید وقتی ما میگیم دوباره درختو بارسازی میکنیم از چه الگوریتمی استفاده میکنیم؟؟
یه چیزی شبیه همون Heapify درسته؟؟؟من هیپ در نظر گرفتم برای همین با اون گفتم
ولی حرف شما درسته حتما هیپ نیست!!ولی میتونه هیپ باشه
در رابطه با حذف هم به نظر من اندیس عنصر رو داریم.ببخشید میشه بگید اگه اندیس عنصر رو نداریم چجوری توی زمان لگاریتم عنصر رو پیدا میکنید؟؟؟
ببین توی پرانتز اومده درخت دودویی کامل رو توضیح داده و تهش هم گفته که مثلا هیپ یک درخت دودویی کامل است.
نگفته که داده ساختار D یک هیپه، توی خط اول ذکر شده که اعداد فقط در برگ های اون ذخیره میشن یعنی شبیه درخت انتخابی که شکلش رو توی ارسال قبلی ضمیمه کردم. خط آخر هم گفته شده که هر گره داخلی فقط کوچکترین مقدار دو فرزندش رو داره. این دو تا ویژگی اصلا در مورد هیپ صادق نیست. بعضی جاها به اون Tournaments as Heaps گفته شده و شایدم selection tree . البته با این تعریف ها میشه گفت یه نوع هیپه که عناصر تکرار داره .
واسه پیدا کردن عنصری که اندیسش رو نداریم من فکر کردم یه الگوریتمی شبیه الگوریتم جستجو در هیپ، رو میشه اینجا هم داشت که واسه هر حالتی الزاما درست نیست! باید اندیس اون رو داشت تا بشه در زمان Logn حذف بشه و دوباره درخت بازسازی بشه در غیر اینصورت باید تو زمان n پیداش کرد و بعد عملیات حذف و بازسازی انجام بشه که دیگه log n نیست. در صورت سوال هم که نگفته اندیس عنصر رو داریم پس اینجوری میشه گزینه 3؟؟!!!
(02 دى 1393 07:29 ب.ظ)ana9940 نوشته شده توسط: [ -> ]ببین توی پرانتز اومده درخت دودویی کامل رو توضیح داده و تهش هم گفته که مثلا هیپ یک درخت دودویی کامل است.
نگفته که داده ساختار D یک هیپه، توی خط اول ذکر شده که اعداد فقط در برگ های اون ذخیره میشن یعنی شبیه درخت انتخابی که شکلش رو توی ارسال قبلی ضمیمه کردم. خط آخر هم گفته شده که هر گره داخلی فقط کوچکترین مقدار دو فرزندش رو داره. این دو تا ویژگی اصلا در مورد هیپ صادق نیست. بعضی جاها به اون Tournaments as Heaps گفته شده و شایدم selection tree . البته با این تعریف ها میشه گفت یه نوع هیپه که عناصر تکرار داره .
واسه پیدا کردن عنصری که اندیسش رو نداریم من فکر کردم یه الگوریتمی شبیه الگوریتم جستجو در هیپ، رو میشه اینجا هم داشت که واسه هر حالتی الزاما درست نیست! باید اندیس اون رو داشت تا بشه در زمان Logn حذف بشه و دوباره درخت بازسازی بشه در غیر اینصورت باید تو زمان n پیداش کرد و بعد عملیات حذف و بازسازی انجام بشه که دیگه log n نیست. در صورت سوال هم که نگفته اندیس عنصر رو داریم پس اینجوری میشه گزینه ۳؟؟!!!
ببینید خودتون دارید میگید که گره داخلی مقدارش همون مقدار کوچکترین فرزندشه پس میتونیم بگیم که یه مین هیپ داریم درسته؟؟
(الان اون درختی که خودتون کشیدید هم یه مین هیپه دیگه)
در ضمن اونطوری که من میدونم در حذف فرض بر اینه که اندیس رو میدن چون اگه اینطور نباشه نمیشه توی زمان لگاریتم عنصر رو پیدا کرد.کلید سوال هم که گزینه 4 بوده
(02 دى 1393 05:32 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببینید فک نکنم سوالو اشتباه فهمیده باشم.سوال گفته یه داده ساختار داریم که درخت دودویی کامل هستش.مگه هیپ درخت دودویی کامل نیستش؟؟؟خود سوال هم گفته مثل هیپ
در ضمن ببینید وقتی ما میگیم دوباره درختو بارسازی میکنیم از چه الگوریتمی استفاده میکنیم؟؟
یه چیزی شبیه همون Heapify درسته؟؟؟من هیپ در نظر گرفتم برای همین با اون گفتم
ولی حرف شما درسته حتما هیپ نیست!!ولی میتونه هیپ باشه
در رابطه با حذف هم به نظر من اندیس عنصر رو داریم.ببخشید میشه بگید اگه اندیس عنصر رو نداریم چجوری توی زمان لگاریتم عنصر رو پیدا میکنید؟؟؟
من با توجه به حل تستا تحلیل کردم .چون بلد نبودم پسیدم .پس تحلیلم اشتباس.
میشه درمورد اندیس توضیح بدید.
باتشکر
(02 دى 1393 01:03 ق.ظ)miladcr7 نوشته شده توسط: [ -> ] (02 دى 1393 12:30 ق.ظ)mariy نوشته شده توسط: [ -> ] (02 دى 1393 12:15 ق.ظ)miladcr7 نوشته شده توسط: [ -> ]حل سوال ۴۲
ببینید کافیه عنصر [tex]i[/tex]ام رو حذف کنیم و سپس اخرین عنصر ارایه رو جای این عنصر بذاریم(خب تا اینجا هر کاری کردیم از مزتبه زمانی [tex]\theta(1)[/tex] بودش).حالا ممکنه با این جا به جایی که انجام دادیم خاصیت MaxHeap ارایه رو از بین برده باشیم ،پس کافیه یه بار الگوریتم Heapify رو اجرا کنیم و بعد دوباره MaxHeap داریم.زمان اجرای الگوریتم Heapify هم [tex]\theta(Logn)[/tex] میشه.پس گزینه ۲ درسته
در هیپ حذف از ریشه صورت میگیره ریشه حذف بشه از مرتبه یک وبرسی هیپ بودن log n .ولی اگه عنصر مورد نظر ریشه نبود یه عنصر خاص بود چطو؟توهمین سوالم گفته iبین ۱ وn چطور عنصر مورد نظر ریشه بگیرم شاید منظورش یه عنصر خاصه که دراین صورت فکر کنم n log n .
خیلی ممنون
ببینید نیازی نیست حتما حذف از ریشه صورت بگیره!!مثلا میگه میخوایم عنصر ۵ رو حذف کنیم و ما هم از طریق اندیس بهش دسترسی پیدا میکنیم و این کار از مرتبه ۱ هستش
پس حذف عنصر با اندیس میشه ازمرتبه یک وبررسی هیپ بون میشه لگاریتم که جواب 2میشه دیگه.logn?خیلی ممنونم ازجواباتون
(02 دى 1393 09:16 ب.ظ)mariy نوشته شده توسط: [ -> ] (02 دى 1393 05:32 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببینید فک نکنم سوالو اشتباه فهمیده باشم.سوال گفته یه داده ساختار داریم که درخت دودویی کامل هستش.مگه هیپ درخت دودویی کامل نیستش؟؟؟خود سوال هم گفته مثل هیپ
در ضمن ببینید وقتی ما میگیم دوباره درختو بارسازی میکنیم از چه الگوریتمی استفاده میکنیم؟؟
یه چیزی شبیه همون Heapify درسته؟؟؟من هیپ در نظر گرفتم برای همین با اون گفتم
ولی حرف شما درسته حتما هیپ نیست!!ولی میتونه هیپ باشه
در رابطه با حذف هم به نظر من اندیس عنصر رو داریم.ببخشید میشه بگید اگه اندیس عنصر رو نداریم چجوری توی زمان لگاریتم عنصر رو پیدا میکنید؟؟؟
من با توجه به حل تستا تحلیل کردم .چون بلد نبودم پسیدم .پس تحلیلم اشتباس.
میشه درمورد اندیس توضیح بدید.
باتشکر
(02 دى 1393 01:03 ق.ظ)miladcr7 نوشته شده توسط: [ -> ] (02 دى 1393 12:30 ق.ظ)mariy نوشته شده توسط: [ -> ] (02 دى 1393 12:15 ق.ظ)miladcr7 نوشته شده توسط: [ -> ]حل سوال ۴۲
ببینید کافیه عنصر [tex]i[/tex]ام رو حذف کنیم و سپس اخرین عنصر ارایه رو جای این عنصر بذاریم(خب تا اینجا هر کاری کردیم از مزتبه زمانی [tex]\theta(1)[/tex] بودش).حالا ممکنه با این جا به جایی که انجام دادیم خاصیت MaxHeap ارایه رو از بین برده باشیم ،پس کافیه یه بار الگوریتم Heapify رو اجرا کنیم و بعد دوباره MaxHeap داریم.زمان اجرای الگوریتم Heapify هم [tex]\theta(Logn)[/tex] میشه.پس گزینه ۲ درسته
در هیپ حذف از ریشه صورت میگیره ریشه حذف بشه از مرتبه یک وبرسی هیپ بودن log n .ولی اگه عنصر مورد نظر ریشه نبود یه عنصر خاص بود چطو؟توهمین سوالم گفته iبین ۱ وn چطور عنصر مورد نظر ریشه بگیرم شاید منظورش یه عنصر خاصه که دراین صورت فکر کنم n log n .
خیلی ممنون
ببینید نیازی نیست حتما حذف از ریشه صورت بگیره!!مثلا میگه میخوایم عنصر ۵ رو حذف کنیم و ما هم از طریق اندیس بهش دسترسی پیدا میکنیم و این کار از مرتبه ۱ هستش
پس حذف عنصر با اندیس میشه ازمرتبه یک وبررسی هیپ بون میشه لگاریتم که جواب ۲میشه دیگه.logn?خیلی ممنونم ازجواباتون
جوابتون رو کامل پایین نوشتم.ببینید درباره اندیس هم مثلا میگه محتویات خونه 5 رو حذف کن ما مستقیما بدون هیچ جست و جویی به خونه 5 دسترسی داریم پس مرتبه این کار 1 هستش
(02 دى 1393 07:59 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببینید خودتون دارید میگید که گره داخلی مقدارش همون مقدار کوچکترین فرزندشه پس میتونیم بگیم که یه مین هیپ داریم درسته؟؟
(الان اون درختی که خودتون کشیدید هم یه مین هیپه دیگه)
در ضمن اونطوری که من میدونم در حذف فرض بر اینه که اندیس رو میدن چون اگه اینطور نباشه نمیشه توی زمان لگاریتم عنصر رو پیدا کرد.کلید سوال هم که گزینه ۴ بوده
آره درست میگی، میشه گفت که درخت تورنمنت یه نوعی از MinHeap هست ولی خب یه درخت خاص تریه نسبت به هیپ، ولی بازم واسه حذف من قانع نمیشم. اگه با فرض MinHeap بریم جلو، حذف از ریشه و بازسازی هیپ میشه logn ولی اگه با فرض خاص بودن درخت تورنمنت بریم جلو، تنها در صورتی حذف یک عنصر (که در تورمنت یه برگ میشه) از logn هست که اندیس اون رو داشته باشیم. خب صورت سوال نگفته اندیس رو داریم، من تو این موارد تست رو حل نمیکنم.
ولی راه حل شما هم درسته.
(02 دى 1393 12:30 ق.ظ)mariy نوشته شده توسط: [ -> ] (02 دى 1393 12:15 ق.ظ)miladcr7 نوشته شده توسط: [ -> ]حل سوال ۴۲
ببینید کافیه عنصر [tex]i[/tex]ام رو حذف کنیم و سپس اخرین عنصر ارایه رو جای این عنصر بذاریم(خب تا اینجا هر کاری کردیم از مزتبه زمانی [tex]\theta(1)[/tex] بودش).حالا ممکنه با این جا به جایی که انجام دادیم خاصیت MaxHeap ارایه رو از بین برده باشیم ،پس کافیه یه بار الگوریتم Heapify رو اجرا کنیم و بعد دوباره MaxHeap داریم.زمان اجرای الگوریتم Heapify هم [tex]\theta(Logn)[/tex] میشه.پس گزینه ۲ درسته
در هیپ حذف از ریشه صورت میگیره ریشه حذف بشه از مرتبه یک وبرسی هیپ بودن log n .ولی اگه عنصر مورد نظر ریشه نبود یه عنصر خاص بود چطو؟توهمین سوالم گفته iبین ۱ وn چطور عنصر مورد نظر ریشه بگیرم شاید منظورش یه عنصر خاصه که دراین صورت فکر کنم n log n .
خیلی ممنون
ببینید اگه حذف از ریشه صورت نگیره باید اندیس عنصر حذف شده رو بدن در غیر این صورت مرتبه پیدا کردن عنصری که میخوایم حذف کنیم از لگاریتم بیشتره.ببین ما برای داده ساختار این سوال میتونیم هیپ رو در نظر بگیریم خب !!!و برای حذف عنصری به غیر از ریشیه فرض بر اینه که
اندیس عنصری که میخوایم حذف کنیم رو داریم چون توی هیپ میشه گفت اصلا جست و جو یه چیز بی معناست.اگه کدایی که برای حذف عنصر به غیر از ریشه نوشته شده رو هم ببینی(برای هیپ) میبینی همه با فرض اینه که اندیس عنصر رو داریم
توی این سوال هم دقیقا همینجوری فرض شده