گروه تلگرامی برنامه نویسان advertise
advertise
دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

12000 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

3000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

4800 تومان
دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

3000 تومان
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

3000 تومان

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

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

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

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

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

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

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

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

 

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

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

الگوریتم درج گره در هیپ

ورودی : مقداری که باید در هیپ قرار گیرد.

خروجی : هیپ با گره جدید

     1. مقدار جدید را در موقعیت بعدی در پایین هیپ قرار دهید.

     2. تا زمانیکه مقدار جدید در ریشه قرار نگرفت و مقدار جدید از والدینش بزرگتر است، مرحله 3 را انجام دهید.

    3. مقدار جدید را با والدینش عوض کنید، بطوریکه مقدار جدید به بالاتر منتقل شود.

 

 

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

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

الگوریتم حذف گره ای از هیپ

ورودی : مقداری که باید از هیپ حذف شود.

خروجی : هیپ با حذف یک گره

   1. مقدار موجود در گره ریشه را حذف کنید و اخرین مقدار هیپ را به جای آن قرار دهید. آخرین مقدار هیپ را با x نشان میدهیم.

   2. تا زمانیکه مقدار x دارای فرزند است و x کوچکتر از فرزندان خود میباشد، مرحله 3 را انجام دهید.

   3. x را با فرزند بزرگتر جابه جا کنید و x را به سمت پایین هیپ حرکت دهید.

 

 

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

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

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

 

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

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

 

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

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

 

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
آموزش ساختمان داده Queue در هیپ heapالگوریتم حذف گره ای از هیپعملیات هیپ در ساختمان دادهعملیات درج در ساختمان داده هیپآموزش ساختمان داده هیپ heapعملیات حذف از ساختمان داده heapنمایش آرایه هیپ heapساختمان داده هیپ heap چیست؟نحوه پیاده سازی ساختمان داده هیپ heapMax heap در Data Structureآشنایی با ساختمان داده ی هیپ heap لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php