اینکه آقای skv میگن من حساب میکنم ۸تا میشه و این دوستمون میگن ۱۴تا ،واسه این هست که یکی تعدادسطوح رو ۹گرفته یکی ۱۰
واسه ارتفاع هیپ داریم: log 1023 +1=10 (حدپاییین لگاریتم رو در نظر میگیریم )
پس ما ۱۰تا سطح داریم
آقامحمد اگه طبق مثال خودتون هم بریم با توجه به مثالی که واسه ۷تا گره زدین و۳سطح داشتیم پس واسه ۱۰۲۳ هم ۱۰ میشه یعنی logn+1
پس با ۱۰ تا گره طبق اون شکلی که آقای skvگذاشتن پیش میریم
که من با اجازه شون اعداد رو هم توی شکل گذاشتم که با توجه به شکل فقط ۸تا برگ بزرگتر از ۱۰۰۰هستند
(۲۷ دى ۱۳۹۱ ۰۹:۳۰ ب.ظ)csharpisatechnology نوشته شده توسط: نکته ای که خودم بهش رسیدم اینه :
اگه ما در یک ماکس هیپ، n گره داشته باشیم به طوری که n، (توانی از ۲ ) منهای یک باشد(مثلا ۲^۴ -۱ = ۱۵) ،درخت حتما پر خواهد بود .لازم نیست این مطلبو حفظ کنیم.بلکه با کشیدن یک شکل ساده می تونیم درکش کنیم.
![[تصویر: 154563_1_1379086454.gif]](https://img.manesht.ir/154563_1_1379086454.gif)
این ۱۴ تا گره ی سطح آخر که از ۱۰۰۰ بزرگترن، به نظر شما پدرشون باید کیا باشن ؟؟؟؟!!!!!!!!!
آیا گره ی مونده که بزرگتر از اینا باشه و به عنوان پدر واسشون انتخاب کنیم ؟؟؟؟!!!!!!!
اصلا ربطی به سطوح نداره جناب maryam.raz.
--
من همه چیزو اثبات کردم.
---
چند نکته طبق کتاب پروفسور قدسی:
سطح ریشه یک است و بقیه ی سطوح به ترتیب یکی یکی زیاد میشن.
دقت کنید که منظور از عمق همون سطح هست.
و دقت کنید که عمق(سطح) ، با ارتفاع فرق داره.
ارتفاع درخت میشه ارتفاع ریشه. یعنی طول بلندترین مسیر رو به پایین تا برگ.
عمق درخت میشه عمق (سطح)آخرین برگ.
ارتفاق درخت، یکی کمتر از عمق درخت هست.
------------
جوابی که دادم کامل هست.
لطفا دوباره بخونیدش
ضمنا ما ۱۰ سطح داریم و ارتفاع ۹ هست. و هیچ جایی رو اشتباه نکردم.
ضمنا جناب skv7 ، پدر گره ها هم مهم نیست.هر چی باشه فقط گره های ۱ تا ۱۰۱۴ می تونن برگ باشن. در صورتی که ادعا می کنید گره ی دیگه ای می تونه برگ باشه مثال من رو نقض کنید. در ضمن سطح ریشه حتما باید ۱ فرض بشه و ارتفاع برگ ها هم صفر هست و ارتفاع درختی با ۱۰۲۳ گره اگه maxHeap باشه میشه ۹ و تعداد سطوحش میشه ۱۰/
اگه در مورد سطح و ارتفاع می خواید بدونیدفقط جزوه ی دکتر قدسی از دانشگاه شریف رو بخونید.
هر سوال دیگه ای هم بود یا تاپیک بزنید یا خصوصی بپرسید رفع ابهام کنم.زیرا جوابی که دادم کامل هست.
maryam.raz که گفتید : که من با اجازه شون اعداد رو هم توی شکل گذاشتم که با توجه به شکل فقط ۸تا برگ بزرگتر از ۱۰۰۰هستند
----------
پاسختون :
دقت کنید که ما می تونیم جابجاییهارو انجام بدیم به طوری که باز هم هر گره از فرزندانش بزرگتر باشه و درخت ماکس هیپ بشه.یعنی بعضی برگ ها می تونند تغییر کنند.ولی در کل همون گره های تا ۱ تا ۱۰۱۴ طبق نکاتی که گفتم باید بتونند توی برگ های قرار بگیرند در غیر اینصورت درخت maxHeap نخواهد بود. می تونید نکته ای رو که توی عکس نشون دادم توی یه مثال طبق همون شکل که گفتم تست کنید.
این مطلبی که میگین درسته
من قبول دارم که گره با شماره ۱۰۱۴ هم میتونه برگ باشه
ولی نمیتونیم بگیم از ۱تا ۱۰۱۴ هم میتونه برگ باشه
آخه اگه ۱۴ تا برگ داریم اونم توی سطح ۱۰، چه جوری میتونیم فقط با ده تا گره واسشون والدهایی بذاریم که تا ریشه برسه؟
اگه طبق گفته خودتون ۱۰تا سطح داریم پس شکل ما درسته دیگه
شما اگه لطف کنید از روی همین شکل این ۱تا ۱۰۱۴ رو بنویسید با والدهایی که بزرگترن ممنون میشیم
بالاخره باید به جواب یکسان برسیم
دوست من ، من نمی گم ۱۴ تا گره بزرگتر از ۱۰۰۰ همزمان می تونه برگ باشه.
بلکه می گم گره هایی که می تونند توی این ماکس هیپ جزو برگ ها باشن فقط می تونن از بین گره های ۱ تا ۱۰۱۴ انتخاب بشن. یعنی فقط این گره ها می تونن برگ باشن.
حالا سوال خواسته از بین این گره ها مشخص کنیم چند تاشون از ۱۰۰۰ بزرگ ترن که از ۱۰۰۱ میشه تا ۱۰۱۴ دیگه.
توی سوال گفته کدوم گره ها می تونه برگ باشن(و تعداد برگ ها رو نخواسته)(تعداد گره های هر سطح میشه ۲ به توان (سطح منهای ۱)(دقت کنید که سطح ریشه حتما از ۱ شروع خواهد شد)
فقط گفته کدوم گره ها می تونن برگ باشن.
منم جواب دقیق رو دادم و صد در صدر جوابی که من دادم بر طبق سوالی که مطرح فرمودن درست هست.
اگه خوب دقت کنید و سوال رو بخونید می بینید جواب من از همه کامل تره.خواهش می کنم از همه ی دوستان تمام جواب های من رو خوب بخونید و عکسی که گذاشتم رو هم ببینید.
شما میاد ابتدا ۱۰۲۳ رو با ۱ جمع می کنید میشه ۱۰۲۴ حالا لگاریتمشو در مبنای ۲ می گیرید میشه ۱۰ پس ۱۰ سطح داریم حالا میاید از ۱۰۲۳ میشمارید تا سطح ۱۰ میشه :
چپ ترین گره سطح ۱: ۱۰۲۳
چپ ترین گره سطح ۲: ۱۰۲۲
چپ ترین گره سطح ۳: ۱۰۲۱
چپ ترین گره سطح ۴: ۱۰۲۰
چپ ترین گره سطح ۵: ۱۰۱۹
چپ ترین گره سطح ۶: ۱۰۱۸
چپ ترین گره سطح ۷: ۱۰۱۷
چپ ترین گره سطح ۸: ۱۰۱۶
چپ ترین گره سطح ۹: ۱۰۱۵
چپ ترین گره سطح ۱۰: ۱۰۱۴
----------------
![[تصویر: 1024BigLeaf.gif]](https://img.manesht.ir/1024BigLeaf.gif)
می فهمیم که بزرگترین برگ باید ۱۰۱۴ باشه.
پس گره های ۱ تا ۱۰۱۴ فقط می تونن برگ باشن.(نمی گم همه ی اینا همزمان_بلکه میگم بعضی از اینها می تونن با هم برگ باشن و فقط برگ ها باید از همین مجموعه باشه و عدد دیگه ای نخواهد بود)
------------
نکته :قانون داریم که ثابت شده گره های ۱ تا بزرگترین برگ می تونند توی ماکس هیپ برگ باشن.
اگه باور ندارید مثالی میزنم :
یه ماکس هیپ با ۱۵ گره رسم کنید(دقت کنید که طبق این سوال تعداد گره های ماکس هیپمون باید توانی از ۲ منهای یک باشه مثل ۲ به توان ۴ منهای ۱ که میشه ۱۶-۱=۱۵ )
حالا ۱۵+۱ میشه ۱۶ از ۱۶ لگاریتم می گیریم میشه ۴ سطح.
حالا میاید از ۱۵میشمارید تا سطح ۴میشه :
چپ ترین گره سطح ۱: ۱۵
چپ ترین گره سطح ۲: ۱۴
چپ ترین گره سطح ۳: ۱۳
چپ ترین گره سطح ۴: ۱۲
-----
می فهمیم که بزرگترین برگ باید ۱۲باشه.
پس گره های ۱ تا ۱۲ فقط می تونن برگ باشن
همچنین در سطح آخر باید ۲ به توان(۴-۱) گره یا ۸ گره داشته باشیم.
این ۸ برگ فقط باید از توی اعداد ۱ تا ۱۲ انتخاب بشن تا درختمون maxHeap باشه(یعنی هر گره از فرزندانش بزرگتر باشه)
اثباتشم توی سه مدل شکل دیگه نشون میدم(تورو خدا قبول کنید حرفام درسته خسته شدم از دستتون):
![[تصویر: 16_maxHeap.gif]](https://img.manesht.ir/16_maxHeap.gif)
همونطور که معلومه گره های ۱ تا ۱۲ باید برگ باشن و ۱۳و۱۴و۱۵ نمی تونن.
هرجورم جابجایی میخواید انجام بدید به شرطی که هرگره از فرزنداش بزرگتر باشه.
دمش گرم fatima1537،که فقط ایشون حرفمو قبول کرد.دیگه توضیح نمیدم.چون جوابم کامل بود.بقیه رو خودتون فکر کنید.مطمئنم جوابم کامله.خواهش می کنم دقت کنید روی توضیحاتم
کاملا حرف csharpisatechnology درسته میشه ۱۴ تا. به همین دلیل که بزرگترین مقدار باید تو ریشه باشه و دومین مقدار بزرگ می تونه در سطح ۲ باشه و سومین مقدار بزرگ می تونه در سطح دو یا سه باشه، چهارمین میتونه در سطح دو،سه یا چهار باشه و الی آخر بنابراین. بنابراین در سطح آخر میشه ۱۰۱۴ قرار بگیره، همچنین اعداد کوچکتر که میشه ۱۴ تا
فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.
(۲۹ دى ۱۳۹۱ ۰۳:۰۸ ب.ظ)mahdiii نوشته شده توسط: فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.دقیقا همینطوره
من هم اون موقعی که جواب دادم منظورم پاسخ قسمت اول بود که توی ارسالم هم گفته بودم.روی بخش دوم سئوال فکر نکرده بودم.
(۲۹ دى ۱۳۹۱ ۰۳:۰۸ ب.ظ)mahdiii نوشته شده توسط: فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.
ممنون ابهامو برطرف کردی ، چند نفر داشتن قسمت اول سوالو حل میکردن ما هم قسمت دومو .در اصل بی دقتی از دو طرف بوده که منظوره همو نمیگرفتیم.
به امید پیشرفت علم
سوال هیچ اشکالی نداره و ابهامی هم در کار نیست دوستان.تحلیل دوستان اشتباست.موفق باشید.
(۳۰ دى ۱۳۹۱ ۰۱:۴۱ ق.ظ)csharpisatechnology نوشته شده توسط: سوال هیچ اشکالی نداره و ابهامی هم در کار نیست دوستان.تحلیل دوستان اشتباست.موفق باشید.
دوست عزیز .خوب سوال دو قسمته .تازه قسمت دوم به صورت صریح گفته همزمان.اگه این سوال همین شکلی تو کنکور میومد من ۸ میزدم (اگه تو گزینه ها بود)و گرنه نمیزدم.
احتمالا این تست نبوده وتمرین بوده
عکس قبلی هم یه جا سطح رو ۹ نوشته بودم اینم اصلاح کامل :
![[تصویر: 155909_1_1379086382.gif]](https://img.manesht.ir/155909_1_1379086382.gif)
(۳۰ دى ۱۳۹۱ ۱۱:۰۶ ق.ظ)svk7 نوشته شده توسط:انشاءا... طراح سوال جواباشو طوری میده که ابهام نباشه.در غیراینصورت اگه سوال دیگه ای دادن اعتراض می کنن دوستان.(30 دى ۱۳۹۱ ۰۱:۴۱ ق.ظ)csharpisatechnology نوشته شده توسط: سوال هیچ اشکالی نداره و ابهامی هم در کار نیست دوستان.تحلیل دوستان اشتباست.موفق باشید.
دوست عزیز .خوب سوال دو قسمته .تازه قسمت دوم به صورت صریح گفته همزمان.اگه این سوال همین شکلی تو کنکور میومد من ۸ میزدم (اگه تو گزینه ها بود)و گرنه نمیزدم.
احتمالا این تست نبوده وتمرین بوده
ضمنا در هر انجمن سعی میشه یه سوال پرسیده بشه.
اون سوالی که می گید همزمان یه چیز دیگست که مهم تر از این بحث هست و نیاز هست یه تاپیک جدای کامل رو هم به اون اختصاص بدیم.
همینطوری هم ننویسید ۸ تا چون اثباتش خیلی مهمه.
پیروز باشید.
از skv گل هم عذر می خوام.من قسمت دوم سوالو به خاطر بی دقتی خودم ندیده بودم.
اما اون ۸ باید یه فرمول کلی هم براش بدست آورد.خیلی مهمه اگه دوستان نکته ی دیگه ای راجع به اون ۸ یاد دارن اضافه کنن ممنون میشم.
برای رسم شکل زیر چه نکته ای رو باید دونست دوستان ؟ :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
منظورتون رو متوجه نمیشم.
این درخت نشون میده که نهایتا ۸ تا گره بزرگتر یا مساوی ۱۰۰۰ رو میشه در برگها به طور همزمان قرار داد