ساختمان داده هیپ heap

ساختمان داده هیپ heap

ساختمان داده هیپ نوعی درخت دودویی است  ولی با درخت جست وجوی دودویی متفاوت میباشد. در هیپ مقدار موجود در هر گره بزرگتر از تمام مقادیر موجود در زیر درخت های آن گره است. پس بزرگترین مقدار در ریشه قرار میگیرد و هر والد از فرزندان خود بزرگتر است.

ساختمان داده های هیپی که بزرگترین مقدار در ریشه قرار دارد max heap نامیده میشوند و به همین ترتیب min heap نوعی هیپ است که در آن، هر مقدار گره کوچکتر از مقادیر فرزندانش است و گره حاوی کوچکترین مقدار میباشد.

Max heap یک درخت دودویی کامل است که خواص زیر را  داراست:

• مقدار موجود در ریشه بزرگتر یا مساوی تمام مقادیر موجود در درخت است.

• هر زیردرخت یک هیپ است.

 

درج در ساختمان داده هیپ :

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

 

 

حذف از ساختمان داده هیپ :

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

 

 

پیاده سازی ساختمان داده هیپ :

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

بنابراین، برای گره ای در موقعیت p فرزند چپ آن در موقعیت 2p و فرزند راست آن در موقعیت 2p+1 قرار دارد. برای گره ای در مکان i، والد آن در مکان i/2 واقع است. اگر i=1 باشد، آن گره ریشه است و والد ندارد.

 

درج در هیپ در نمایش آرایه :

در نمایش آرایه ی هیپ، اگر بخواهیم مقدار جدیدی را درج کنیم، باید آنرا در آخرین خانه ی آرایه قرار دهیم . این کار معادل قرار دادن مقدار جدید در موقعیت سمت راست و پایین هیپ است که در ساختار درختی داشتیم. اکنون مقدار جدید را باید با والد آن مقایسه کنیم (در موقعیت i/2) و اگر مقدار جدید از مقدار والدش بزرگتر بود آنها را جابه جا میکنیم و تا وقتی به اولین مکان آرایه (ریشه درخت هیپ) و یا به حالتی برسیم که مقدار جدید از والدش کوچکتر باشد، این کار را تکرار میکنیم.

 

حذف از هیپ در نمایش آرایه :

در حذف عنصر از هیپ نیز، همیشه باید عنصر موجود در بالای هیپ و در نمایش آرایه باید اولین مقدار موجود در مکان 1 آرایه را حذف کنیم. برای حذف اولین مقدار، آخرین عنصر موجود در آرایه را به جای آن قرار میدهیم و سپس آنرا جابه جا میکنیم تا در موقعیت مناسبی از آرایه قرار گیرد. برای جابه جا کردن مقدار باید آنرا با مقدار فرزندان چپ و راستش در موقعیتهای 2p و 2p+1 مقایسه کنیم و اگر از آنها کوچکتر بود با فرزند بزرگتر جابه جا گردد.