advertise laitec sharif univercity
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

10000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

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

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

10000 تومان
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

68000 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

48000 تومان

ساختمان داده هیپ 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
عملیات هیپ در ساختمان دادهعملیات حذف از ساختمان داده heapالگوریتم حذف گره ای از هیپساختمان داده هیپ heap چیست؟Max heap در Data Structureآموزش ساختمان داده Queue در هیپ heapنمایش آرایه هیپ heapآموزش ساختمان داده هیپ heapنحوه پیاده سازی ساختمان داده هیپ heapعملیات درج در ساختمان داده هیپآشنایی با ساختمان داده ی هیپ heap لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

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

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