سلام دوستان
در مورد این سوال با توجه به اینکه صورت سوال گفته عناصر "متمایز" به نظر من جواب گزینه سه هست ولی در کتاب مقمسی گفته شده همه موارد و در جواب نوشته : در درخت max-heap فرزندان یک گره می توانند مساوی باشند !! نظر شما چیه؟
![[تصویر: 211587_1_1379079794.png]](https://img.manesht.ir/211587_1_1379079794.png)
سلام.
با فرض متمایز بودن همه‌ی عناصر داریم:
عنصر اول همیشه در درایه‌ی یک قرار داره.
عنصر دوم همیشه یا در درایه‌ی دوم یا در درایه‌ی سوم قرار داره (حتماً فرزند عنصر اوله).
عنصر سوم یا بابد مستقیم فرزند عنصر اول باشه یا فرزند عنصر دوم. پس اگه عنصر دوم در درایه‌ی دو باشه عنصر سوم میتونه توی درایه‌های ۳، ۴ یا ۵ باشه و اگه عنصر دوم در درایه‌ی ۳ باشه عنصر سوم میتونه توی درایه‌های ۲، ۶ یا ۷ باشه.
عنصر چهارم هم باید مستقیماً فرزند عنصر اول، دوم یا سوم باشه، پس در مجموع این خونه‌ها براش امکان‌پذیره:
۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، ۱۱، ۱۲، ۱۳، ۱۴، ۱۵
بنابراین همه موارد گزینه‌ی صحیح است. اون توضیح اضافه‌ای که کتاب مقسمی داده (که فرزندان گره می‌تونن مساوی باشند) مال اینه که حل کننده‌ی سؤال دلیل درست بودن گزینه‌ی ۴ رو اشتباه فهمیده ;-)
(۲۱ شهریور ۱۳۹۲ ۰۶:۴۰ ب.ظ)azk84 نوشته شده توسط: سلام.ممنون از پاسختون ولی مگه طبق تعریف درخت heap که درخت کامل هست عنصر سوم نباید حتما" فرزند عنصر اول باشه ؟ اگه فرزند عنصر دوم باشه قانون کامل بودن نقض میشه که ؟؟!
با فرض متمایز بودن همه‌ی عناصر داریم:
عنصر اول همیشه در درایه‌ی یک قرار داره.
عنصر دوم همیشه یا در درایه‌ی دوم یا در درایه‌ی سوم قرار داره (حتماً فرزند عنصر اوله).
عنصر سوم یا بابد مستقیم فرزند عنصر اول باشه یا فرزند عنصر دوم. پس اگه عنصر دوم در درایه‌ی دو باشه عنصر سوم میتونه توی درایه‌های ۳، ۴ یا ۵ باشه و اگه عنصر دوم در درایه‌ی ۳ باشه عنصر سوم میتونه توی درایه‌های ۲، ۶ یا ۷ باشه.
عنصر چهارم هم باید مستقیماً فرزند عنصر اول، دوم یا سوم باشه، پس در مجموع این خونه‌ها براش امکان‌پذیره:
۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، ۱۱، ۱۲، ۱۳، ۱۴، ۱۵
بنابراین همه موارد گزینه‌ی صحیح است. اون توضیح اضافه‌ای که کتاب مقسمی داده (که فرزندان گره می‌تونن مساوی باشند) مال اینه که حل کننده‌ی سؤال دلیل درست بودن گزینه‌ی ۴ رو اشتباه فهمیده ;-)
منظور از سومین عنصر همون سومین بزرگ‌ترین عنصره. تنها شرط هیپ ماکزیمم در زمینه‌ی ترتیب چیدن عناصر (به جز شرط کامل بودن) اینه که هر عنصر از دو فرزندش باید بزرگ‌تر باشه، بنابراین مثلاً چهارمین بزرگ‌ترین عنصر میتونه به این شکل توی درایه‌ی هشتم قرار بگیره:
[tex]\textbf{[15]}\textbf{[14]}[11]\textbf{[13]}[10][9][8]\mathbf{[12]}[7][6]...[/tex]
(۲۱ شهریور ۱۳۹۲ ۰۷:۳۲ ب.ظ)azk84 نوشته شده توسط: منظور از سومین عنصر همون سومین بزرگ‌ترین عنصره. تنها شرط هیپ ماکزیمم در زمینه‌ی ترتیب چیدن عناصر (به جز شرط کامل بودن) اینه که هر عنصر از دو فرزندش باید بزرگ‌تر باشه، بنابراین مثلاً چهارمین بزرگ‌ترین عنصر میتونه به این شکل توی درایه‌ی هشتم قرار بگیره:
[tex]\textbf{[15]}\textbf{[14]}[11]\textbf{[13]}[10][9][8]\mathbf{[12]}[7][6]...[/tex]
بله حرفتون کاملا" درسته .. ممنون بابت پاسختون
(۲۱ شهریور ۱۳۹۲ ۱۱:۵۸ ب.ظ)tabassomesayna نوشته شده توسط:(21 شهریور ۱۳۹۲ ۰۷:۳۲ ب.ظ)azk84 نوشته شده توسط: منظور از سومین عنصر همون سومین بزرگ‌ترین عنصره. تنها شرط هیپ ماکزیمم در زمینه‌ی ترتیب چیدن عناصر (به جز شرط کامل بودن) اینه که هر عنصر از دو فرزندش باید بزرگ‌تر باشه، بنابراین مثلاً چهارمین بزرگ‌ترین عنصر میتونه به این شکل توی درایه‌ی هشتم قرار بگیره:
[tex]\textbf{[15]}\textbf{[14]}[11]\textbf{[13]}[10][9][8]\mathbf{[12]}[7][6]...[/tex]
بله حرفتون کاملا" درسته .. ممنون بابت پاسختون
خواهش می‌کنم ;-)
(۲۱ شهریور ۱۳۹۲ ۰۶:۱۱ ب.ظ)tabassomesayna نوشته شده توسط: سلام دوستان
در مورد این سوال با توجه به اینکه صورت سوال گفته عناصر "متمایز" به نظر من جواب گزینه سه هست ولی در کتاب مقمسی گفته شده همه موارد و در جواب نوشته : در درخت max-heap فرزندان یک گره می توانند مساوی باشند !! نظر شما چیه؟
![[تصویر: 211736_1_1379079384.png]](https://img.manesht.ir/211736_1_1379079384.png)
شما به این نکته توجه کنید که k امین عنصر در سطحی بیشتر از k نمیتونه قرار بگیره، (اگه بگیره دیگه K امین نیست) و از طرفی، عنایت داشته باشید که عنصر سطح i ام میتونه توی درایه های [tex]\[ 2^{i} \dots 2^{i 1}-1\][/tex] قرار بگیرن که با توجه به این موضوع، ۴ امین عنصر میتونه توی سطح اول یعنی درایه های ۲ تا ۳ و یا سطح سوم درایه هاس ۸ تا ۱۵ و یا سطح دوم که میشه درایه های ۴ تا ۷، که با توجه به این مقدمات میشه گزینه ۴ بدون هیچ سر دردی
