یک هیپ مورب ( یا خود سازگار شونده ) یک داده ساختار به صورت هیپ است که مانند یک درخت دودویی پیاده سازی شده است. هیپ های مورب در مقایسه با هیپ های دودویی با سرعت بیشتری ادغام می شوند. برخلاف هیپ های دودویی، هیچ محدودیتی در ساختار هیپ مورب وجود ندارد، در نتیجه هیچ تضمینی نیست که ارتفاع درخت از مرتبهٔ لگاریتمی باشد. تنها دو شرط باید در هیپ مورب برقرار باشد:
• مرتبهٔ کلی هیپ باید داده شده باشد.
• هر عملیاتی که روی دو هیپ مورب قابل انجام است ( مانند جمع، حذف عنصر کمینه و ادغام ) ، باید با استفاده از یک الگوریتم خاص برای ادغام انجام شود.
هیپ مورب، یک نوع درخت چپ گرا است که از طریق جا به جایی همهٔ گره ها هنگام ادغام، تعادل هیپ را حفظ می کند. ( عملیات ادغام همچنین در جمع و حذف مقادیر به کار برده می شود. )
ممکن است هیپ مورب به دلیل نداشتن محدودیت های ساختاری، نامناسب و غیرمفید به نظر بیاید. اگرچه، با استفاده از تحلیل سرشکنی می توان نشان داد که تمام عملیات روی هیپ مورب را می توان در ( O ( logn انجام داد. [ ۱]
هیپ های مورب با استفاده از الگوریتم بازگشتی زیر تعریف می شوند:
• یک هیپ با تنها یک عنصر، هیپ مورب است.
• ادغام دو هیپ مورب، یک هیپ مورب تولید می کند.
می توان از الگوریتمی مشابه با ادغام دو درخت چپ گرا استفاده کرد:
• مقایسهٔ ریشهٔ دو هیپ؛ هیپ با ریشهٔ کوچکتر را p و هیپ دیگر را q در نظر می گیریم. هیپ حاصل را نیز r می نامیم.
• ریشهٔ هیپ r را برابر با ریشهٔ p ( ریشهٔ کوچکتر ) ، و به جای زیردرخت راست r، زیردرخت چپ p را قرار می دهیم.
• زیردرخت چپ r را با ادغام زیردرخت راست p و هیپ q به صورت بازگشتی محاسبه می کنیم.
قبل :
بعد :
یک الگوریتم غیربازگشتی هم وجود دارد، که طولانی تر است و در ابتدا به مرتب سازی نیاز دارد.
• هر هیپ را با جدا کردن سمت راست ترین مسیر به چند زیردرخت تقسیم می کنیم. ( با شروع از ریشه، گرهٔ سمت راست را جدا کرده و فرزند راست آن را زیردرختش قرار می دهیم. ) با این روش، مجموعه ای از درخت ها تولید می شوند که ریشهٔ آن ها فقط فرزند چپ دارد یا اصلاً فرزند ندارد.
• زیردرخت ها را به ترتیب صعودی مقادیر ریشه شان مرتب می کنیم.
• از سمت راست دو زیردرخت آخر را با هم ادغام می کنیم و این کار را تکرار می کنیم تا زمانی که به یک درخت برسیم.
• اگر ریشهٔ زیردرخت یکی مانده به آخر، فرزند چپ داشته باشد، آن را با فرزند راست جا به جا می کنیم.
• ریشهٔ آخرین زیردرخت را به جای فرزند چپ زیردرخت یکی مانده به آخر قرار می دهیم.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف• مرتبهٔ کلی هیپ باید داده شده باشد.
• هر عملیاتی که روی دو هیپ مورب قابل انجام است ( مانند جمع، حذف عنصر کمینه و ادغام ) ، باید با استفاده از یک الگوریتم خاص برای ادغام انجام شود.
هیپ مورب، یک نوع درخت چپ گرا است که از طریق جا به جایی همهٔ گره ها هنگام ادغام، تعادل هیپ را حفظ می کند. ( عملیات ادغام همچنین در جمع و حذف مقادیر به کار برده می شود. )
ممکن است هیپ مورب به دلیل نداشتن محدودیت های ساختاری، نامناسب و غیرمفید به نظر بیاید. اگرچه، با استفاده از تحلیل سرشکنی می توان نشان داد که تمام عملیات روی هیپ مورب را می توان در ( O ( logn انجام داد. [ ۱]
هیپ های مورب با استفاده از الگوریتم بازگشتی زیر تعریف می شوند:
• یک هیپ با تنها یک عنصر، هیپ مورب است.
• ادغام دو هیپ مورب، یک هیپ مورب تولید می کند.
می توان از الگوریتمی مشابه با ادغام دو درخت چپ گرا استفاده کرد:
• مقایسهٔ ریشهٔ دو هیپ؛ هیپ با ریشهٔ کوچکتر را p و هیپ دیگر را q در نظر می گیریم. هیپ حاصل را نیز r می نامیم.
• ریشهٔ هیپ r را برابر با ریشهٔ p ( ریشهٔ کوچکتر ) ، و به جای زیردرخت راست r، زیردرخت چپ p را قرار می دهیم.
• زیردرخت چپ r را با ادغام زیردرخت راست p و هیپ q به صورت بازگشتی محاسبه می کنیم.
قبل :
بعد :
یک الگوریتم غیربازگشتی هم وجود دارد، که طولانی تر است و در ابتدا به مرتب سازی نیاز دارد.
• هر هیپ را با جدا کردن سمت راست ترین مسیر به چند زیردرخت تقسیم می کنیم. ( با شروع از ریشه، گرهٔ سمت راست را جدا کرده و فرزند راست آن را زیردرختش قرار می دهیم. ) با این روش، مجموعه ای از درخت ها تولید می شوند که ریشهٔ آن ها فقط فرزند چپ دارد یا اصلاً فرزند ندارد.
• زیردرخت ها را به ترتیب صعودی مقادیر ریشه شان مرتب می کنیم.
• از سمت راست دو زیردرخت آخر را با هم ادغام می کنیم و این کار را تکرار می کنیم تا زمانی که به یک درخت برسیم.
• اگر ریشهٔ زیردرخت یکی مانده به آخر، فرزند چپ داشته باشد، آن را با فرزند راست جا به جا می کنیم.
• ریشهٔ آخرین زیردرخت را به جای فرزند چپ زیردرخت یکی مانده به آخر قرار می دهیم.
wiki: هرم مورب