باز سرو کله درخت هیپ پیدا می شود!

پرسش:‌ برنامه ای بنویسید که k لیست مرتب شده را در هم ترکیب نماید و یک لیست کل مرتب شده به طول n را برگرداند.

پاسخ: حل مساله را با یک مثال شروع می کنیم. اگر سه لیست مرتب شده زیر را داشته باشیم:
[13, 12, 9, 5, 1] و [7, 3] و [15, 10, 8]

آنگاه حاصل ترکیب آنها یک لیست به طول 10 و بصورت [15, 13, 12, 10, 9, 8, 7, 5, 3, 1] خواهد بود.

یک راه حل بدیهی برای این مساله آن است که لیست ها را بدون در نظر گرفتن ترتیب به هم وصل کنیم و سپس لیست کل بوجود آمده را مرتب نماییم تا به لیست کل مرتب دست یابیم. پیچیدگی محاسباتی این الگوریتم ((O(n*log(n می باشد. اشکال این الگوریتم آن است که از خاصیت مرتب بودن لیست ها استفاده نمی کند و بنابر این کار اضافی انجام می دهد.

برای یک راه حل بهینه تر می توانیم از خاصیت مرتب بودن لیست ها استفاده کنیم تا یک به یک عناصر را در جای درستشان بنشانیم. مثلا مشاهده می کنیم که کوچکترین عنصر لیست کل مرتب اولین عنصر یکی از لیست ها می باشد. در مثال بالا، این مقدار 1 است که از لیست اول است زیرا کوچکترین مقدار بین کوچکترین مقادیر لیست ها است. برای یافتن کوچکترین عنصر بعدی باید عنصر دوم از لیست اول به همراه عنصر اول لیست های دیگر در نظر گرفته شوند. با دنبال کردن این مثال به یک الگوریتمی می رسیم.

در یک الگوریتم بهینه هر بار مینیمم بین کوچکترین عنصر استفاده نشده لیست ها را می یابیم و در انتهای لیست ترکیبی درج می کنیم.

در یک مصاحبه باید الگوریتم مطرح شده را روی یک مثال اجرا کنیم تا مطمئن شویم که درست کار می کند. شکل زیر قسمتی از این اجرا را نشان می دهد.

بنابر این کلیات الگوریتم درست کار می کند.

برای پیاده سازی الگوریتم فوق نیاز به یک لیست از مینیمم ها داریم که از k عنصر که هر یک مینیمم استفاده نشده در یکی از لیستهاست تشکیل می شود. در این الگورتیم هر بار (۱) مقدار مینیمم بین این k مقدار را پیدا کنیم و (۲) آن را پس از استفاده از لیست مینیمم ها حذف کنیم، و (۳) مقدار بعدی استفاده نشده از لیستی که مقدار مینیمم از آن انتخاب شد را در لیست مقادیر مینیمم درج کنیم.

پیدا کردن مینیمم بین یک لیست به طول k دارای پیچیدگی محاسباتی (O(k می باشد. با توجه به اینکه این لیست بروز می شود و هر بار باید مقدار مینیمم جدید را محاسبه کنیم، این الگوریتم دارای پیچیدگی محاسباتی (O(n*k خواهد بود.

واقعیت این است که اگر در لیست k عنصری مینیمم ها تنها مقدار عناصر را بگذاریم نمی توانیم پس از یافتن عنصر مینیمم به راحتی بفهمیم که این عنصر مربوط به کدام یک از لیستها بوده است. بنابر این همراه با مقادیر، اندیس لیستی که مقدار متعلق به آن است و اندیس موقعیت عنصر در آن لیست باید نگهداری شود.

با توجه به اینکه نیاز به یک لیست داریم که بتواند سریع عنصر مینیمم را بیابد بنظر می رسد که درخت هیپ می تواند موثر باشد. قبل از محاسبه هزینه کل الگوریتم در صورت استفاده از یک درخت هیپ به جای یک درخت معمولی، باید موارد ذیل را در مورد یک درخت هیپ با اندازه k یادآوری کنیم:

۱- هزینه یافتن عنصر مینیمم (O(1 می باشد.

۲- هزینه حذف عنصر مینیمم و بازسازی درخت هیپ ((O(log(k می باشد.

۳- هزینه اضافه کردن یک عنصر و بازسازی درخت هیپ ((O(log(k می باشد.

در الگوریتم فوق این اتفاقات در ارتباط با درخت هیپ اتفاق می افتد: هربار عنصر مینیمم از لیست مینیمم ها را پیدا می کنیم. این کار در درخت هیپ دارای هزینه (O(1 می باشد. سپس باید این عنصر را از لیست مینیمم ها حذف کنیم که هزینه آن ((O(log(k می باشد. نهایتا باید عنصر بعدی از لیستی که عنصری از آن را استفاده کردیم را به لیست مینیممها اضافه کنیم که هزینه آن (log(k می باشد. این کار باید برای همه n عنصر لیست کل انجام شود. بنابر این هزینه این الگوریتم در صورت استفاده از درخت هیپ ((O(n*log(k هست که سرعت آن بسیار بهتر از سرعت نسخه اول این الگوریتم است که از یک لیست عادی استفاده می کند.

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

با توجه به مثال فوق الگوریتم روی مثال بالا بدرستی عمل می کند. بنابراین آن را پیاده می کنیم.

ابتدا ماژول های مناسب را برای استفاده در ساختمان داده درخت هیپ در برنامه وارد می کنیم (خط 1). سپس نام تابع و پارامترهای مناسب را تعریف می کنیم (خط 2). تعداد لیست های داده شده را می شماریم (خط 3). سپس همه عناصر اول لیستها را در یک درخت هیپ می گذاریم. برای هر عنصر علاوه بر مقدار اندیس لیستی که از آن انتخاب شده اند و اندیس عنصر (0 که نشان دهنده عنصر اول است) را نیز قرار می دهیم (خط 4). سپس لیست را تبدیل به درخت هیپ می کنیم (خط 5). آنگاه یک لیست خالی از جواب ها می سازیم (خط 6). سپس تا زمانی که درخت هیپ تمام نشده است یک حلقه تکرار را انجام می دهیم (خط 8 تا 12). هر بار عنصر بالای درخت هیپ را به عنوان مینیمم تا این نقطه برمی داریم (خط 9). سپس آن را به لیست جوابها اضافه می کنیم (خط 10). سپس مقدار بعدی از لیستی که عنصر آن استفاده شده را به درخت هیپ اضافه می کنیم (خط 11 و 12). با اتمام حلقه لیست پاسخ را برمی گردانیم (خط 13).

در یک مصاحبه واقعی برنامه را دوباره مرور می کنیم و با داده های تستی امتحان می کنیم.