Categories
ساختمان داده

ساختار داده هیپ (Heap)

ساختار داده هیپ – Heap (هرم)

ساختار داده هیپ یک ساختار داده شبه درخت است که برای یافتن حداقل و حداکثر مقدار در یک لیست از مقادیر بهینه شده است.

درخت دودویی کامل یک درخت دودویی هست که به تمام مراحل کاملا پر شده اند به جز پایینترین مرحله. 

مقدار حداقل یا حداکثر در ریشه هر درخت ذخیره می‌شود. در یک آرایه این مقدار در موقعیت صفر قرار می‌گیرد. در این صورت ما یک درخت دودویی کامل داریم و میتوانیم گره سمت چپ هر گره را با 2i+1 و گره سمت راستش را با 2i + 2 و گره والد را با floor((i-1)/2) بطوریکه i شاخص گره میباشد بدست آوریم.

چه موقع از هیپ در مصاحبه ها استفاده کنیم؟

هیپ ها زمانیکه به دنبال مقدار مینیمم و یا ماکسیمم در یک لیست هستید بهترین گزینه هستند.

میتوانید از هیپ ها برای مرتب کردن یک لیست و یا پیدا کردن N عدد برتر در لیست نیز استفاده کنید.

هیپ ها برای جستجو و یا دسترسی تصادفی مقادیری که ذخیره میکنند مناسب نیستند. 

محاسبه میزان استفاده از حافظه

از آنجاییکه هیپ ها معمولا به صورت یک آرایه نمایش داده میشوند،‌ میزان حافظه کمی علاوه بر آرایه اشغال میکنند. در حقیقت،‌ هیپ ها بر پایه یک الگوریتم مرتب سازی درجا به نام heapsort هستند،‌ پس میتوانید بدون نیاز به حافظه اضافی یک هیپ با استفاده از یک آرایه بسازید!

Leave a Reply

Your email address will not be published. Required fields are marked *