بخش ۸: درخت هیپ

پرسش: یک لیست k-مرتب داده شده است به این معنا که هر عنصری از این لیست حداکثر K خانه از موقعیت کاملا مرتب آن فاصله دارد. برنامه ای بنویسید که این لیست را مرتب کند.پاسخ: حل مساله را با یک مثال شروع می کنیم. لیست [1, 3, 4, 2, 6, 5] یک لیست 3-مرتب است زیرا هر عنصر آن حداکثر سه خانه از موقعیت آن در لیست مرتب شده یعنی [6, 5, 4, 3, 2, 1] فاصله دارد. مثلا مقدار 2 باید درخانه اندیس 1 باشد درحالیکه در اندیس 3 قرار گرفته است. به عبارت دیگر برای مرتب کردن لیست، هیچ عنصری نیاز به جابجایی بیش از 3 خانه ندارد.بدیهی است که برای مرتب کردن این لیست می توان ازالگوریتم های مرتب سازی لیست استفاده نمود. این روشها معمولا پیچیدگی محاسباتی ((O(n*log(n دارند.

اما با توجه به اینکه این لیست تقریبا مرتب است باید بتوان با هزینه کمتری آن را مرتب نمود. درواقع به این دلیل که هر عنصری در فاصله k از موقعیت درستش می باشد، با n بار مرتب سازی زیر لیست هایی به طول 2k+1 می توانیم لیست را مرتب کنیم. پیچیدگی محاسباتی چنین الگوریتمی ((O(n*k*log(k می باشد. با اندکی دقت بیشتر متوجه می شویم که برای هر عنصر لیست تنها نیاز به مرتب کردن k+1 عنصر، شامل خودش و k عنصر بعد آن داریم. مثلا اگر برای یافتن مقداری که در موقعیت صفر لیست قرار می گیرد تنها نیاز به مرتب کردنk+1 عنصر اول لیست می باشد. با این کار طبق تعریف لیست k-مرتب عنصر اول در بین این k+1 عنصر است که با مرتب سازی آنها در محل درست قرار می گیرد.

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

درخت هیپ: ساختمان داده درخت هیپ (هرم) مینیمم یک درخت دودویی است با این خاصیت ویژه که مقدار هر گره پدر از گره های فرزند کوچکتر است. همینطور درخت هیپ ماکزییم یک درخت دودویی است که مقدار هر گره پدر از گره های فرزند بزرگتر است. برای اینکه این ساختمان داده را بیاد آورید می توانید درخت برگزاری مسابقات ورزشی را تجسم کنید زیرا در آن قهرمان لیگ در بالاست که از همه بهتر است. درخت هیپ کاربردهای زیادی دارد. بخصوص زمانی که نیاز به محاسبه مقدار مینیمم یک سری داده است که مرتبا بروز می شوند.

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

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

با توجه به درست بودن اجرا روی مثال از درستی الگوریتم اطمینان حاصل می کنیم.سپس شروع به پیاده سازی الگوریتم می کنیم. ابتدا ماژولهایی که برای ایجاد یک درخت هیپ لازم است را در برنامه وارد می کنیم (خط 1). سپس تابع با پارامترهای مناسب را تعریف می کنیم (خط 3). در ابتدای تابع یک لیست خالی تعریف می کنیم که برای نگهداری درخت هیپ بکار خواهیم برد (خط 4). سپس ابتدا با پیشروی در لیست به اندازه k خانه یک درخته k عنصری ایجاد می کنیم (خط 5 تا 6). سپس در یک حلقه تکرار هر بار کوچکترین عنصر درخت هیپ را از آن بر می داریم و در موقعیت i ام لیست می گذاریم. آنگاه عنصر بعدی که در درخت هیپ درج نشده است را در آن درج می کنیم (خطوط 10 و 11). آنگاه سراغ عنصر بعدی لیست می رویم (خط 12). زمانی که درخت هیپ خالی شود یعنی همه عناصر را در جای درستشان نشانده ایم.

from heapq import heappush, heappop
def sort_k_unsorted_array(arr, k):
	knext = []
	for _ in range(min(k+1, len(arr))):
		heappush(knext, arr[_])
	i = 0
	while knext:
		arr[i] = heappop(knext)
		if i < len(arr)-k-1:
			heappush(knext, arr[i + k + 1])
		i += 1
	return arr

پرسش:‌ برنامه ای بنویسید که 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). سپس نام تابع و پارامترهای مناسب را تعریف می کنیم (خط 3). تعداد لیست های داده شده را می شماریم (خط 4). سپس همه عناصر اول لیستها را در یک درخت هیپ می گذاریم. برای هر عنصر علاوه بر مقدار اندیس لیستی که از آن انتخاب شده اند و اندیس عنصر (0 که نشان دهنده عنصر اول است) را نیز قرار می دهیم (خط 6 و 7). سپس لیست را تبدیل به درخت هیپ می کنیم (خط 8). آنگاه لیست خالی از جواب ها می سازیم (خط 9). سپس تا زمانی که درخت هیپ تمام نشده است یک حلقه تکرار را انجام می دهیم (خط 11). هر بار عنصر بالای درخت هیپ را به عنوان مینیمم تا این نقطه برمی داریم (خط 12). سپس آن را به لیست جوابها اضافه می کنیم (خط 13). سپس مقدار بعدی از لیستی که عنصر آن استفاده شده را به درخت هیپ اضافه می کنیم (خط 15 و 16). با اتمام حلقه لیست پاسخ را برمی گردانیم (خط 18).

from heapq import heappush, heappop, heapify
def merge_k_sorted_array(arrs):
	k = len(arrs)
	heap = [(arrs[i][0], i, 0) for i in range(k) if len(arrs[i])>0]
	heapify(heap)
	res = []

	while heap:
		minv, arr_index, index = heappop(heap)
		res.append(minv)
		if index<len(arrs[arr_index])-1:
			heappush(heap, (arrs[arr_index][index+1], arr_index, index+1))
	return res





GiottoPress by Enrique Chavez