مکس-هیپ

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

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

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

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

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

منبع

  • T. Cormen (۱۰ نوامبر ۲۰۱۱Introduction to Algorithms، MIT Press، ص. ۱۵۲-۱۵۳ تاریخ وارد شده در |تاریخ= را بررسی کنید (کمک)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.