{CodeGate}

هیپ در جاوا (heap implementation)

در این آموزش تیم کدگیت را با توضیح هیپ (heap) یا هرم در جاوا همراهی کنید. برای درک بهتر این آموزش پیشنهاد می شود آموزش های قبلی ساختمان داده مانند لینک لیست یا پشته را مطالعه کنید.

هیپ (Heap)

در علوم رایانه، هرم یا هیپ (heap) یک ساختمان دادهی درخت (ساختار داده) است که شرط «اگر B بچه A بود، آنگاه مقدار گره A بزرگتر مساوی مقدار گره B باشد» را ارضا کند. این مسئله بیانگر این است که گره با بیشترین مقدار همواره در ریشه قرار می‌گیرد و بنابراین چنین هیپی، هیپ بیشینه نامیده می‌شود. بر روی این که هر گره چند گره فرزند داشته باشد، هیچ محدودیتی وجود ندارد، حال آنکه در عمل معمولاً هر گره، دو فرزند دارد. هیپ یک داده ساختار بهینه برای پیاده‌سازی یک داده انتزاعی به نام صف اولویت دار می‌باشد. هیپ‌ها در الگوریتم‌های زیادی مانند الگوریتم دیکسترا در نظریه گراف کاربرد دارند(ویکیپدیا).

هیپ در جاوا

درخت دودویی کامل

یک درخت دودویی کامل است، هرگاه تمامی سطوح درخت به غیر از احتمالا آخرین سطح پر بوده و برگ‌های سطح آخر از سمت چپ قرار گرفته باشند.

هیپ در جاوا

هرم دودویی

هرم دودویی یک داده‌ساختار هرم است که از یک درخت دودویی استفاده می‌کند. می‌توان به این داده‌ساختار به عنوان یک درخت دودویی نگاه کرد با این تفاوت که باید دو محدودیت را در نظر بگیریم. اول اینکه‌ای درخت، درخت دودویی کامل است، در همه سطح‌های این درخت این ویژگی برقرار است به جز احتمالاً سطح اخر که در سطح اخر گره‌ها از چپ به راست پر هستند (خاصیت ظاهری). و مورد دوم اینکه همه گره‌ها از فرزندشان کوچک‌تر مساوی (یا بزرگ‌ترمساوی) هستند. اگر همه گره‌ها از فرزندانشان کوچک‌تر مساوی باشند هرم کمینه و اگر همه گره‌ها بزرگ‌تر مساوی از فرزندانشان باشند هرم بیشینه نامگذاری می‌شوند (خاصیت هرم). اغلب برای پیاده‌سازی صف اولویت از هرم کمینه استفاده می‌شود.

نمایش هرم دودویی

هرم دودویی اگر بخواهیم با لیست پیوندی نمایش دهیم نیاز به سه اشاره گر داریم برای جست و جوی رو به پایین و رو به بالا(هر نود به فرزندان خود و پدرش اشاره دارد) پیاده سازی این کار ساده است ولی همیشه یک درخت دودویی کامل ما را به یاد آرایه می اندازد و از این رو پیاده سازی هرم با آرایه کاره ساده تری است. با آرایه دیگر ما از اشاره گر استفاده نمیکنیم و کل کار ما با اندیس آرایه است. برای نمایش هرم دودویی، اگر نودی در خانه i بود فرزندان آن در خانه 2i+1 و 2i هستند.

هیپ در جاوا

پیاده سازی هیپ بیشینه

برای پیاده سازی هرم بیشینه ابتدا به توضیح متد های کمکی این کار میپردازیم و سپس به طور کامل آن را پیاده سازی میکنیم.

متدهای less و exch برای مقایسه و جابجایی دو نود از هرم استفاده میشود.

متد swim زمانی استفاده میشود که نودی از پدرش بزرگتر شود و ما نیاز داریم تا شرط هرم بیشینه را رعایت کنیم به همین دلیل باید مکان مناسبی برای این نود در درخت ایجاد شده پیدا کنیم و هیچ شرطی هم نقض نشود. ما نود بزرگتر را با پدرش جابجا میکنیم و اگر نود جابجا شده از تمام فرزندان بزرگتر بود ممکن است دوباره مشکل اول برای ما پیش بیاید یعنی نودی که جابجا کردیم از پدرش بزرگتر باشد پس همین کار را ادامه میدهیم تا دیگر نتوانیم جابجایی انجام دهیم.متد swim این کار را انجام میدهد.

هیپ در جاوا

متد sink موقعی استفاده میشد که نود پدر از فرزندانش کوچکتر باشد. در این صودت ما باید مکانی برای این نود پیدا کنیم که شرط هرم نقض نشود. برای این کار ما نود پدر را با بزرگترین نود فرزند جا به جا میکنیم و اگر دوباره اتفاق بزرگ بودن پدر رخ داد، همین جابجایی را انجام میدهیم تا دیگر نتوانیم نودی را جابجا کنیم. کاره متد sink این است.

هیپ در جاوا

حال دو متد insert  و remove max را توضیح میدهیم. متد  insert یک نود را به هرم اضافه میکند برای این کار ما یک نود به آخر آرایه اضافه میکنیم و متد swim که توضیح داده شد را صدا میزنیم تا شرط هیپ برقرار باشد. کاری که متد remove max انجام میدهد این است که به جای نود اول نود آخر قرار میدهد و متد sink را صدا میزند تا دوباره هیپ ساخته شود.

هیپ در جاوا

حال به پیاده سازی هرم بیشینه میپردازیم. کل کد در یک کلاس به نام maxheap مینویسیم.

خروجی کد بالا به صورت زیر است:

پسورد: www.codegate.ir

 

دسته : java, جاوا, ساختمان داده در جاوا, گراف در جاوا

Tags:  , , ,

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz