سوالاتی مثل
سومین کوچکترین کلید در یک min هیپ با کلید های متمایز در درایه هایی با چه اندیس هایی است
و
یک max هیپ با n عنصر متمایز را در نظر بگیرید که با آرایه پیاده سازی شده است چهارمین بزرگترین عنصر در کدام یک از درایه ها می تواند باشد؟
چه جوری استدلال می شن؟؟
سلام.
r اُمین کوچکترین کلید در Max-Heap میتونه بین ۲ تا [tex]2^r -1[/tex] اُمین عنصر باشه.
مثلا سومین بزرگترین عدد میتونه توی گرههای ۲ تا ۷ باشه.
این قانون رو شما یاد بگیر. اثباتش رو با عدد گذاری و تحلیل میتونی بدست بیاری.
قاعدتا این قانون برای Min-Heap هم برقراره.
ببینید در یک min heap کوچکترین کلید که حتما در ریشه است. --> بدیهی
برای بقیه چند حالت پیش میاد :
۱- دو تا کلید کوچک بعدی می تونند فرزندان اول ریشه باشند. --> دومین و سومین کوچکترین کلید : گره های ۲و۳
۲- چون توی هیپ دو تا زیر درخت از هم متمایزند (منظورم اینه که فقط باید گره های زیر درخت از ریشه بزرگتر باشه و به زیر درخت سمت چپ کاری نداره) پس شما یک زیر درخت رو کلا نادیده بگیر و توی اون یکی زیر درخت یکی رو بذار دومین کوچکترین کلید و در فرزندان اون گره شروع کن اعداد رو به ترتیب بچین.--> سومین کوچکترین کلید میشه گره ۴ یا ۵
۳- همین حالت تو زیردرخت سمت راست میتونه اتفاق بیفته. ---> سومین کوچکترین کلید میشه گره ۶ یا ۷
و .... تا سطح های بعد
با توجه به این چیزایی که گفتین می تونم در نظر بگیرم ککه n امین کوچکترین کلید در min هیپ و n امین بزرگ ترین کلید در max هیپ از کلیدیک ( ریشه ) تا کلید های سطح n هست؟
بله.
البته بجز ریشه. فرمولی که دادم هم بیانگر همین موضوع هست.