هرم کمینه بیشینه

در علوم رایانه، هرم کمینه بیشینه یک درخت دودویی کامل است که فواید هرم کمینه و هرم بیشینه را با هم ترکیب کرده است. این ساختمان داده به ما این امکان را می دهد تا عنصر بیشینه و کمینه را
در زمان ثابت ( ( 1 ) O ) بازگرداند یا در زمان لگاریتمی ( ( logn ) O ) آن ها را حذف کنیم. [ ۱] این قابلیت هرم کمینه بیشینه را به یک ساختمان داده مفید برای پیاده سازی یک صف اولویت دو طرفه تبدیل می کند.
همانند هرم کمینه و هرم بیشینه دودویی، هرم کمینه بیشینه عملیات های درج و حذف را در زمان لگاریتمی انجام می دهد و در زمان خطی ساخته می شود. [ ۲] هرم کمینه بیشینه معمولا در آرایه ساخته می شود [ ۳] به همین دلیل به عنوان یک ساختمان داده ضمنی از آن یاد می شود.
  مشخصه ی یک هرم کمینه بیشینه  :
هر گره در سطح زوج در درخت دودویی متناظر با هرم از تمام گره های موجود در زیردرخت خود کوچکتر است درحالی که هر گره در سطح فرد در درخت متناظر با هرم از تمام گره های زیردرخت خود بزرگتر است. [ ۳]
این ساختار همچنین می تواند به گونه ای تعمیم داده شود تا عملیات هایی مثل پیدا کردن میانه ( find - median ) و ( delete - median ) حذف کردن میانه[ ۱] ، پیدا کردن kامین کوچکترین مقدار در ساختار ( ( find ( k ) و عملیات حذف کردن kامین کوچکترین مقدار در ساختار ( ( delete ( k ) را به ازای یک مقدار مشخص یا مجموعه ای از مقادیر k انجام دهد. این داده ساختار دو عملیات انتهایی را میتواند به ترتیب در زمان های خطی و لگاریتمی انجام دهد. مفهوم ترتیب کمینه بیشینه میتواند به ساختارهای دیگری که بر پایه ترتیب بیشینه یا کمینه هستند گسترش پیدا کند مانند درخت چپ گرا ( leftist trees ) که منجر به ایجاد یک دسته جدید و قدرتمند از داده ساختارها می شود. [ ۳] هرم کمینه بیشینه همچنین برای پیاده سازی مرتب سازی سریع خارجی نیز مفید است.
• هرم کمینه بیشنه یک درخت دودویی کامل است که شامل سطوح کمینه ( زوج ) و بیشینه ( فرد ) است. سطوح زوج 0، 2، 4، . . . و سطوح فرد 1، 3، 5، . . . . همچنین فرض می کنیم عنصر ریشه در سطح اول ( 0 ) قرار دارد.
• عنصر ریشه کوچکترین عنصر موجود در هرم کمینه بیشینه است.
• یکی از دو گره موجود در سطح دوم که سطح بیشینه ( فرد ) است، عنصر بیشینه در هرم کمینه بیشینه است.
• فرض کنید x یک گره دلخواه در هرم کمینه بیشینه است. در این صورت  :
• اگر x در سطح کمینه ( یا زوج ) قرار داشته باشد در اینصورت کلید آن از کلید همه عناصر موجود در زیردرختی که ریشه آن x است کمتر است.
• اگرx   در سطح بیشینه ( یا فرد ) قرار داشته باشد در اینصورت کلید آن از کلید همه عناصر موجود در زیردرختی که ریشه آن x است بیشتر است.