مکس-هیپ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مثالی برای درخت مکس-هیپ

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

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

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

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

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

منبع[ویرایش]

  • T. Cormen. Introduction to Algorithms. MIT Press، ‫۱۰ نوامبر ۲۰۱۱. 152-153.