رایانه

حذف گره از درخت هیپ عموما از ریشه آن صورت می گیرد. حذف گرهی غیر از گره ریشه ممکن است هزینه ای معادل ساخت مجدد درخت تحمیل کند! چرا که با حذف یک گره غیر ریشه و جایگزین کردن گرهی دیگر با آن، نه تنها شرط heap بودن که شرط درخت کامل بودن هم ممکن است نقض شود!!! اکثر کاربردهای این نوع درخت نیز تنها با حذف گره از ریشه سر و کار دارند.

برای گره ریشه درخت دو مرحله زیر را اجرا می کنیم:

1- گره ریشه را حذف و سمت راست ترین برگ سطح آخر را جایگزین آن می کنیم.

2- در صورتی که گره درج شده جدید شرط heap بودن را نقض نکند عملیات حذف تمام می شود. در غیر اینصورت این گره با فرزند مناسب جایگزین شده و این مرحله برای درخت جدید مجددا اجرا می شود.

با اجرای مرحله اول و جایگزین کردن آخرین گره آخرین سطح درخت، شرط کامل بودن درخت پایدار می ماند. اما عموما شرط heap بودن نقض می شود. در مرحله دوم گره تازه وارد را با یکی از فرزندان خود جایگزین می کنیم تا به شرط heap بودن نزدیک شویم. اما کدام فرزند؟ پاسخ را با یک مثال مشخص می کنیم.

فرض کنید قصد داریم گره ریشه درخت min-heap زیر را حذف کنیم:

مرحله اول را اجرا کرده و گره شماره 10 با مقدار 20 را جایگزین ریشه می کنیم:

شرط درخت کامل بودن همچنان برقرار است. اما درخت فعلی min-heap نیست. چرا که ریشه از هر دو فرزند خود بزرگتر است. حال مطابق مرحله دوم باید یکی از فرزندان را با والد جابجا کنیم. اما کدام فرزند؟

اگر فرزند چپ با مقدار 8 را انتخاب کنیم:

در این حالت علاوه بر بحث مکان درست گره شماره 2 با مقدار 20، مشکل دیگری هم داریم: گره شماره 1 و 3 هم شرط min-heap را نقض می کنند!

اگر فرزند راست را انتخاب می کردیم:

در این حالت لااقل گره های شماره 1 و 2 مشکلی ندارند و تنها دغدغه ما محل درست گره شماره 3 خواهد بود!!! پس نتیجه اینکه:

در مرحله عملیات حذف گره در درخت min-heap، فرزندی را جایگزین والد می کنیم که مقدار کوچکتری داشته باشد. این مساله در مورد max-heap به صورت عکس است. یعنی فرزندی را در درخت max-heap جایگزین می کنیم که مقدار بیشتری دارد.

اما هنوز گره شماره 3 شرط min-heap بودن را نقض می کند. پس با تکرار مرحله دوم و با توجه به نتیجه گیری فوق، این گره را با گره شماره 6 جابجا می کنیم:

به این ترتیب شرط min-heap بودن نیز برقرار شده، و عملیات حذف گره به اتمام می رسد.

برنامه نویسی حذف گره از درخت heap:

در این قسمت کد مربوط به حذف گره ریشه درخت min-heap را می آوریم. در مورد درخت max-heap هم با اندکی تغییر به دست می آید.

این عملیات برای درخت فوق در نمایش آرایه ای به فرم زیر خواهد شد:

آ

بر اساس روابط ریاضی بین شماره اندیس گرههای والد و فرزند تابع pop برای حذف گره ریشه به این ترتیب خواهد بود:

int pop ( int heap [ ], int &n )

{

int i = 1, result, temp, min;

result = heap[1];

heap [ 1 ] = heap [ n -- ];

while ( 2 * i <= n )

{

min = 2 * i;

if ( min + 1 <= n && heap [ min + 1 ] < heap [ min ] )

min ++;

if ( heap [ i ] <= heap [ min ] )

break;

temp = heap [ i ];

heap [ i ] = heap [ min ];

heap [ min ] = temp;

i = min;

}

return result;

}

توجه داشته باشید که تابع pop درخت heap به فرم آرایه و تعداد عناصر آن را دریافت کرده و ضمن حذف گره ریشه، مقدار آن را باز می گرداند.

نکته: با توجه به قطعه کد بالا مرتبه اجرایی عمل حذف گره از درخت heap از مرتبه ( O ( log₂n است.