advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

3000 تومان
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

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

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

4800 تومان
دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

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

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

18000 تومان

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

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

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