کارکو advertise laitec sharif univercity تبلیغات در سایت سورس کد
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

دانلود پروژه وب سایت اشعار با ASP.NET و SQL

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

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

3000 تومان
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

3000 تومان
سورس پروژه پایانی آزمون گیری با زبان سی شارپ و SQL

سورس پروژه پایانی آزمون گیری با زبان سی شارپ و SQL

7000 تومان

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

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

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