مکس-هیپ

مکس-هیپ (به انگلیسی: max-heap) درختی دودویی است، که در آن ویژگی هرمی مکس-هیپ به درستی به نمایش در می‌آید. برای هر گره $i$ به جز ریشه عبارت زیر صدق می‌کند:

مثالی برای درخت مکس-هیپ

$A[Parent(i)]>=A[i]$

یعنی، برای هر گره بیشترین مقدار برابر با مقدار گره والدین است. با وجود اینکه بزرگترین عضو در ریشهٔ هرم ذخیره می‌شود و درخت‌هایی که زیر یک ریشه قرار دارند، مقداری بیشتری از گره ندارند.

مقداری که در هر دایره قرار دارد، بزرگی گره مورد نظر است. عددی که بالای هر گره قرار دارد، اندیس آن در آرایه است. بالا و پایین هر گره خطوطی وجود دارند که رابطهٔ والدین-فرزندی را نشان می‌دهند. والدین همیشه در دست چپ فرزندان خود قرار دارند. ارتفاع این هرم مانند دیگر هرم‌ها $\Theta (Logn)$ است.

این هرم در مرتب‌سازی هرمی مورد استفاده قرار می‌گیرد. در مقابل این هرم(درخت)، مین هیپ قرار دارد.

منبع

• T. Cormen (‫۱۰ نوامبر ۲۰۱۱)، Introduction to Algorithms، MIT Press، ص. ۱۵۲-۱۵۳