Algorithm design & data structure

1.1K views09:26

در ساختمان داده، هیپ نوعی ساختار داده درختی است که به عنوان یک درخت دودویی کامل (✅Complete Binary Tree) سازماندهی می‌شود. در این درخت، هر سطح (به‌جز سطح آخر) کاملاً پر شده و گره‌ها به سمت چپ تراز شده‌اند. هیپ به دو نوع اصلی تقسیم می‌شود:

1. Max-Heap (ماکس-هیپ)⬆️
در Max-Heap، مقدار هر گره بزرگتر یا مساوی مقدار فرزندانش است. یعنی، بزرگترین مقدار همیشه در ریشه درخت قرار می‌گیرد. این نوع هیپ برای استخراج حداکثر (extract-max) بسیار کارآمد است.

2. Min-Heap (مین-هیپ)⬇️
در Min-Heap، مقدار هر گره کوچکتر یا مساوی مقدار فرزندانش است. یعنی، کوچکترین مقدار در ریشه قرار دارد. این نوع هیپ برای استخراج حداقل (extract-min) مناسب است.

ویژگی‌های کلیدی هیپ 🌳
- درخت دودویی کامل: هیپ همیشه یک درخت دودویی کامل است، یعنی هر سطح (به‌جز آخرین سطح) به‌طور کامل پر شده است.
- خاصیت هیپ: در Max-Heap مقدار هر گره بزرگتر یا مساوی فرزندانش و در Min-Heap مقدار هر گره کوچکتر یا مساوی فرزندانش است.

عملیات‌های اصلی هیپ 🔄
1. افزودن عنصر (Insert) ➕: افزودن یک عنصر جدید به هیپ با قرار دادن آن در اولین جای خالی و سپس "heapify" از پایین به بالا.
2. استخراج حداکثر/حداقل (Extract Max/Min) ➖: حذف عنصر ریشه و جایگزینی آن با آخرین عنصر درخت و سپس "heapify" از بالا به پایین.
3. ایجاد هیپ (Build Heap) 🛠: ساختن هیپ از یک آرایه با استفاده از روش "heapify" برای هر زیر درخت.

کاربردهای هیپ 📚
- الگوریتم‌های مرتب‌سازی: مانند Heap Sort که از خاصیت هیپ برای مرتب‌سازی استفاده می‌کند.
- ساختارهای داده اولویت‌دار: مانند Priority Queue که از هیپ برای مدیریت صف با اولویت استفاده می‌کند.
- مدیریت منابع سیستم: برای تخصیص حافظه و مدیریت فرآیندها در سیستم‌های عامل.

مزایای هیپ 🎯
- پیچیدگی زمانی کارآمد ⏱: عملیات‌های اصلی مانند افزودن، استخراج حداکثر/حداقل، و ساختن هیپ به ترتیب دارای پیچیدگی زمانی( O(log n و O(n) هستند.
- ساختار داده ساده: پیاده‌سازی و استفاده از هیپ به دلیل ساختار ساده آن، نسبتاً آسان است.

هیپ یکی از ساختارهای داده پرکاربرد است که در الگوریتم‌ها و سیستم‌های کامپیوتری به‌طور گسترده‌ای استفاده می‌شود.

#الگوریتم
📣👨‍💻@AlgorithmDesign_DataStructuer

2.8K viewsedited 09:26