پرسش: یک لیست k-مرتب داده شده است به این معنا که هر عنصری از این لیست حداکثر K خانه از موقعیت کاملا مرتب آن فاصله دارد. برنامه ای بنویسید که این لیست را مرتب کند.
پاسخ: حل مساله را با یک مثال شروع می کنیم. لیست [5, 6, 2, 4, 3, 1] یک لیست 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). زمانی که درخت هیپ خالی شود یعنی همه عناصر را در جای درستشان نشانده ایم.
