ببخشید دوستان دیروز تویه پارسه سوال داده بود اما به نظر من اشتباه بود!
آرایه این هست:۱۳,۱۴,۱۶,۱۹,۲۱,۱۹,۶۸,۶۵,۲۶,۳۲,۳۱
گفته که این یه هیپ هست و اگر اعمال زیر رو انجام بدیم ترتیبش تویه آرایه چطوری میشه؟
Del(حذف کوچک ترین عنصر)
Ins وارد کردن عدد جدید
اعمال:
DEL,INS(17),INS(15),DEL,DEL
پیشاپیش از پاسختون ممنونم--------------------------------------------------
یه سوال دیگه : آقا مگه وقتی که ریشه رو حذف میکنیم و سمت راست ترین برگ سطح آخر میره تو ریشه، اول با فرزند چپ مقایسه نمیشه و هیپیفای نمیکنیم و بعدش با فرزند سمت راستش؟
ممنون
(۱۴ بهمن ۱۳۹۱ ۰۳:۵۵ ب.ظ)sir_ams نوشته شده توسط: یه سوال دیگه : آقا مگه وقتی که ریشه رو حذف میکنیم و سمت راست ترین برگ سطح آخر میره تو ریشه، اول با فرزند چپ مقایسه نمیشه و هیپیفای نمیکنیم و بعدش با فرزند سمت راستش؟نه
(۱۴ بهمن ۱۳۹۱ ۰۴:۰۰ ب.ظ)mfXpert نوشته شده توسط:(14 بهمن ۱۳۹۱ ۰۳:۵۵ ب.ظ)sir_ams نوشته شده توسط: یه سوال دیگه : آقا مگه وقتی که ریشه رو حذف میکنیم و سمت راست ترین برگ سطح آخر میره تو ریشه، اول با فرزند چپ مقایسه نمیشه و هیپیفای نمیکنیم و بعدش با فرزند سمت راستش؟نه
آخرین گره برگ رو بجای ریشه قرار میدیم. ریشه رو با ۲i و ۲i+1 مقایسه می کنیم، بسته به ماکس هیپ بودن یا مین هیپ بودن، جایگزینی در فرزندان تفاوت داره. ربطی به اول فرزند چپ و یا فرزند راست نداره.
(۱۴ بهمن ۱۳۹۱ ۰۴:۱۲ ب.ظ)azad_ahmadi نوشته شده توسط: آخرین گره برگ رو بجای ریشه قرار میدیم. ریشه رو با ۲i و ۲i+1 مقایسه می کنیم، بسته به ماکس هیپ بودن یا مین هیپ بودن، جایگزینی در فرزندان تفاوت داره. ربطی به اول فرزند چپ و یا فرزند راست نداره.خب ترتیب نداره؟ مثلا اول با ۲i مقایسه بشه و بعدش ۲i+1؟؟
اگه از هر ۲تا بزرگتر باشه تویه مین هیپ، چی میشه؟ با کوچیکترین جابجا میشه؟ یا به ترتیب مقایسه میشه؟
منظور شما اینه که در هیپ عناصر متمایز نباشند(عناصر تکراری وجود داشته باشه). هیپ این خاصیت رو داره، یعنی میشه مقدار کلید هر گره بزرگتر یا مساوی فرزندان(برای ماکس) و کوچکتر یا مساوی(برای مین) باشه. در این صورت فرقی نمی کنه، در هر صورت در نوشتن تابع هیپیفای اولین شرطی که برقرار باشه انجام میشه.
(۱۴ بهمن ۱۳۹۱ ۰۴:۲۲ ب.ظ)sir_ams نوشته شده توسط: خب ترتیب نداره؟ مثلا اول با ۲i مقایسه بشه و بعدش ۲i+1؟؟خوب وقتی مثلا درخت مین هیپ هست مشخصه دیگه برای مین هیپ باقی موندن باید با گره ای که کوچیکتره جابجا بشه
اگه از هر ۲تا بزرگتر باشه تویه مین هیپ، چی میشه؟ با کوچیکترین جابجا میشه؟ یا به ترتیب مقایسه میشه؟
فرقی نداره اول با کدوم مقایسه میشه
وقتی از هردو بزرگتر باشه باید با فرزندی که فرزند دیگه کوچکتر هست جابجا بشه چون در غیر اینطورت (با فرزندی جابجا بشه که از خودش کوچکتر هست اما اون فرزند از فرزند دیگه بزرگتر هست) مین هیپ ایجاد میشه
پس همزمان باید با هردو فرزند مقایسه کنی و با کوچکترین جابجا کنی
۱۶,۱۷,۱۹,۲۶,۱۹,۲۱,۶۸,۶۵,۳۱,۳۲
سوالش مشکلی نداره
مقایسه با هر دو فرزند انجام میشه هر کدوم کوچکتر بود جایگزین میشه در مین هیپ و برعکسش در ماکس هیپ
متشکرم از همه دوستان
من تا الان اینجوری فکر میکردم که باید اول با چپی مقایسه میشه و اگر بزرگتر بود( برای مین هیپ) باهاش جابجا میشه و بعدش دوباره ریشه با فرزند راست مقایسه میشه! و الان فهمیدم که اشتباه میکردم
و درستش اینه:همزمان با هر دوتا فرزندش مقایشه میشه و با کوچیکترینشون جا به جا میشه!
اگر لشتباه میگم تصحیح کنید لطفا.
متشکرم پیشاپیش
(۱۴ بهمن ۱۳۹۱ ۰۶:۳۹ ب.ظ)sir_ams نوشته شده توسط: و درستش اینه:همزمان با هر دوتا فرزندش مقایشه میشه و با کوچیکترینشون جا به جا میشه!درسته
ببین گفته درخت هیپ هست نگفته ماکس هیپ است یا مین هیپ.
هیپ عادی فکر کنم فقط کامل است.
به نظرم بعد از اعمال فوق خروجی نهایی به صورت زیر از چپ به راست در آرایه درج میشه:
۳۱-۱۵-۱۶-۱۹-۲۱-۱۹-۶۸-۶۵-۲۶-۳۲
---------
بازم بررسی می کنم.دوستان اگه مطالعه کردن مشکلی می بینن بگن.
؟؟؟؟؟؟؟؟؟؟؟؟
درسته فقط گفته هیپه، ولی با توجه به اعداد کاملا مشخصه که مین هیپه دیگه!!!!
(۱۴ بهمن ۱۳۹۱ ۰۷:۴۱ ب.ظ)csharpisatechnology نوشته شده توسط: ببین گفته درخت هیپ هست نگفته ماکس هیپ است یا مین هیپ.
هیپ عادی فکر کنم فقط کامل است.
به نظرم بعد از اعمال فوق خروجی نهایی به صورت زیر از چپ به راست در آرایه درج میشه:
۳۱-۱۵-۱۶-۱۹-۲۱-۱۹-۶۸-۶۵-۲۶-۳۲
هیپ درخت mintree یا maxtree کامل هست
پس هیپ یا min هست یا max
خروجی روهم اشتباه بدست اوردید
آقا آخر نگفتید خروجی من درست هست یا نه. هیپ یا ماکس هست یا مین. هیپ خالی که نداریم. اینجا هم مشخصه که مین هیپ هست.
۱۶,۱۷,۱۹,۲۶,۱۹,۲۱,۶۸,۶۵,۳۱,۳۲
(۱۴ بهمن ۱۳۹۱ ۰۸:۱۱ ب.ظ)narges_r نوشته شده توسط: هیپ درخت mintree یا maxtree کامل هستدوست گرامی لطفا منبع مذکور رو بفرمایید تا ابهامو برطرف کنیم !؟
پس هیپ یا min هست یا max
خروجی روهم اشتباه بدست اوردید
در صورت ادعای رد جواب من، لطفا جواب درست رو که بلدید بنویسید.
در کتاب مقسمی صفحه ی ۲۷۲ فصل هفتم درخت های ویژه گفته :
mintree: درختی که مقدار هر کلید آن کوچکتر یا مساوی کلیدهای فرزندانش باشد.
maxtree: درختی که مقدار هر کلید آن بزرگتر یا مساوی کلیدهای فرزندانش باشد.
--
یه جا دیگه هم درس داده که deap درختی هست که یه طرفش minheap هست و یه طرفش maxheap.
در deap ریشه احتمالا باید تهی باشه و این یعنی چیزی که شما می گید یعنی mintree یا maxtree رو نقض می کنه.
چون ریشه مقدارش null هست.
---
البته روی حرف شما هم شک دارم چون یکم آشناست
انگار منم قبولش دارم ولی لطفا کامل کنید پاسختون رو
(۱۸ بهمن ۱۳۹۱ ۰۴:۱۱ ق.ظ)csharpisatechnology نوشته شده توسط: دوست گرامی لطفا منبع مذکور رو بفرمایید تا ابهامو برطرف کنیم !؟
در صورت ادعای رد جواب من، لطفا جواب درست رو که بلدید بنویسید.
منبع کتاب پوران و پارسه
پاسخ صحیح هم در ارسال ۷ داده شده
(۱۸ بهمن ۱۳۹۱ ۰۴:۱۱ ق.ظ)csharpisatechnology نوشته شده توسط: یه جا دیگه هم درس داده که deap درختی هست که یه طرفش minheap هست و یه طرفش maxheap.
در deap ریشه احتمالا باید تهی باشه و این یعنی چیزی که شما می گید یعنی mintree یا maxtree رو نقض می کنه.
چون ریشه مقدارش null هست.
deap نوعی درخت هست که با درخت heap ساخته میشه! ربطی به این سوال نداره
maxheap درخت maxtree هست که کامل باشه، همینطور برای minheap درخت mintree کامل هست