ساختار داده Heap

ساختار داده هیپ یک ساختار داده بر مبنای درخت که به صورت دودویی هست ایجاد شده. یعنی به صورت باینری پیاده سازی میشه در نتیجه پیچیدگی زمانی ایجادش O(log n) خواهد بود. و تمامی شاخه‌ها بجز ردیف آخر که از سمت چپ شروع به پر کردن می‌کنیم، دو فرزند خواهند داشت. کاربرد اصلیش برای پیدا کردن ماکزیمم و مینیموم در لحظه است که پیچیدگی خوندن ماکس و مین با این روش O(1) خواهد بود.

دونوع Heap داریم:

• نوع Max-Heap: کلیدی که در نود روت قرار داره، بزرگترین از بین همه بچه‌ها خواهد بود و همه بچه‌ها کوچکتر و یا مساوی خواهند بود و این قاعده به طور بازگشتی برای همه زیر درخت‌ها برقراره.
• نوع Min-Heap: کلیدی که در نود روت قرار داره، از همه بچه‌ها کوچکتر یا مساوی خواهد بود و این قاعده برای همه زیر درخت‌ها هم بر قراره.