ساختمان داده ها آشنایی با درخت Heap - قسمت اول
درخت Heap (یا هرم، یا کپه!) از جمله ساختارهای پرکاربرد بحث ساختمان داده هاست. در این مجموعه مقالات سعی می کنم شما را با این ساختار آشنا کرده و مسائل مرتبط با آن را تشریح کنم.
ابتدا با تعریف درخت دودویی کامل شروع می کنیم.
درخت دودویی کامل:
یک درخت دودویی کامل است، هرگاه تمامی سطوح درخت به غیر از احتمالا آخرین سطح پر بوده و برگهای سطح آخر از سمت چپ قرار گرفته باشند.
به یک مثال دقت کنید:
همانطور که مشاهده می کنید تمامی سطوح درخت به غیر از آخرین سطح به طور کامل پر و همه برگهای سطح آخر نیز در سمت چپ درخت هستند. در واقع تمامی برگهای درخت دودویی کامل در دو سطح آخر آن قرار دارند.
نمایش درخت دودویی کامل:
نمایش با استفاده از لیست پیوندی و آرایه دو شکل مشهور نمایش درخت دودویی در ساختمان داده هاست. در حالت عادی انتخاب یکی از این دو روش برای نمایش بهینه و با مصرف حافظه کمتر بسته به چیدمان عناصر درخت دارد. به عنوان مثال در درختهای مورب روش نمایش با آرایه بدترین بازدهی و بیشترین مصرف حافظه را دارد! اما بر عکس، در درخت دودویی کامل این روش در مقایسه با روش لیست پیوندی بسیار بهینه تر است.
در این روش گرههای درخت مطابق شکل فوق با شروع از ریشه و در هر سطح از چپ به راست به ترتیب شماره گذاری شده و مقدار هر کدام از گره ها با توجه به شماره آن در یکی از خانه های آرایه قرار می گیرد. برای درخت فوق داریم:
در آرایه متناظر درخت دودویی کامل از همه عناصر به صورت کامل استفاده شده و هیچ حافظه هرزی تولید نمی شود. (چرا!؟)
فرض کنیم توابع Left ،Parent و Right شماره یک گره را گرفته و به ترتیب شماره گره والد، فرزند چپ و فرزند راست را برگرداند. در این صورت به توجه به شکل فوق داریم:
Parent ( i ) = [ i / 2 ] , Left ( i ) = 2 * i , Right ( i ) = 2 * i + 1
که منظور از [ ] جزء صحیح (کف) عدد است.
به عنوان مثال در مورد گره شماره 3 می توان نوشت:
Parent ( 3 ) = [ 3 / 2 ] = 1 , Left ( 3 ) = 2 * 3 = 6 , Right( 3 ) = 2 * 3 + 1 = 7
با این توضیحات به سراغ تعریف هرم می رویم.
هرم ماکزیمم (ماکس هیپ / max-heap):
درخت دودویی کاملی است که مقدار هر گره بیشتر یا مساوی فرزندان خود است.
به عنوان مثال:
و نمایش آرایه ای:
هرم مینیمم (مین هیپ / min-heap):
درخت دودویی کاملی است که مقدار هر گره کمتر یا مساوی فرزندان خود است.
به عنوان مثال:
و نمایش آرایه ای:
درختهای هیپ (یا هرم، یا کپه!) کاربردهای زیادی دارند که از نوع تعریف و ساختارشان ناشی می شود.
