خانه / کد / الگوریتم و کد Heap Sort

الگوریتم و کد Heap Sort

مرتب سازی هرمی یا  Heap Sort  یکی از بهترین روش های سورت کردن است که از مرتبه (o(n*log n است و از نظر کار آمدی در شبیه سازی حافظه بعد از Quick sort (مرتب سازی سریع) تقریبا بهترین عملکرد را دارد.

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

-bubble sort

-insertion sort

-merge sort

-quick sort

-Distribution sorts

– Concurrent sorts

– Heap sort

-Radix sort

– Counting sort

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

Max Binary Heap Tree  – درخت دودویی هرمی :

درختMax  Binary heap درختی است که تمام گره های آن حداکثر دو فرزند دارند و هر گره مقدارش بزرگ تر مساوی مقدار گره های فرزندش است .

ما برای شبیه سازی این درخت از ساختمان داده های زیادی می توانیم استفاده کنیم ولی برای سهولت در پیاده سازی از آرایه استفاده می کنیم.

ریشه را همیشه در خانه ی اول آرایه می گذاریم و فرزندان  گره ای i ام را در خانه ی ۲i+1 و ۲i+2 قرار می گیرد.

در این ساختار همیشه خانه ی صفرم آرایه بیشترین مقدار را دارد. و از این ویژگی برای مرتب سازی آرایه استفاده می کنیم.

فرض کیند آرایه ای را به شما داده اند و می خواهید آن را به وسیله Heap sort مرتب کنید برای این کار باید آرایه را به صورت Max Heap Tree در آورید برای این این کار از دو تابع به اسم های max_heapify  و make_max_heap  استفاده می کنیم که در ادامه آن را شرح خواهیم داد.

max_heapify :

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

int *arr : آرایه ای است که به صورت اشاره گر فرستاده شده است

int n: تعداد اعضای هر آرایه است

int i : شماره گره ای است که باید تابع روی آن فراخوانی شود

void max_heapify(int*arr,int n,int i)<br />
{<br />
    int left_child = 2 * i + 1;<br />
    int right_child = 2 * i + 2;<br />
    int large = i;<br />
 <br />
    if (left_child &lt; n &amp;&amp; arr[large] &lt; arr[left_child])<br />
    {<br />
        large = left_child;<br />
    }<br />
    if (right_child &lt; n &amp;&amp; arr[large] &lt; arr[right_child])<br />
    {<br />
        large = right_child;<br />
    }<br />
    if (large != i)<br />
    {<br />
        int temp;<br />
        temp = arr[i];<br />
        arr[i] = arr[large];<br />
        arr[large] = temp;<br />
        max_heapify(arr, n, large);<br />
    }<br />
}

make_max_heap :

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

void make_max_heap(int* arr, int n)<br />
{<br />
    for (int i = n / 2 + 1; i &gt;= 0; i--)<br />
    {<br />
        max_heapify(arr, n, i);<br />
    }<br />
}

اگر به کد بالا توجه کنید می بینید ما از خانه ی n/2 آرایه شروع به فراخوانی تابع  max_heapify کرده ایم تا به خانه ی صفر آرایه رسیدم از این کار دو هدف داشته ایم:

یک – اگر از خانه ی صفر شروع به فراخوانی تابع  max_heapify  می کردیم هر بار که آن تابع را فراخوانی می کردیم ممکن بود وضعیت گره ها در پایین عوض شود در نتیجه باید بارها از اول تا آخر این کار را برای تمام خانه های آرایه می کردیم تا آرایه به صورت هیپ در آید ولی وقتی از خانه ی آخر به خانه صفرم این کار را می کنیم دیگر این مشکل پیش نمی آید.

دو – شاید این سوال برای شما پیش آمده باشد چرا از خانه ی n/2 شروع کردیم و از n نکردیم ، به خاطر این که خانه های  n/2 +1 به بعد برگ هستند و فرزندی ندارند که نگران آن باشیم که شرط هیپ برای آن ها برقرار نباشد.

خوب تا اینجا که آمدیم ما یه آرایه را گرفتیم و آن را به صورت درخت Max Heap در آوردیم حالا چطور از این آرایه استفاده کنیم و آرایه مرتب شده را به دست بیاوریم؟

اگر یادتان باشد در بالا گفتیم که یکی از مهمترین ویژگی آرایه ی به وجود آمده این است که خانه صفرم آرایه بزرگ ترین مقدار را در تمام آرایه دارد و ما از همین ویژگی استفاده می کنیم.

تابع heap_sort :

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

در زیر کد مربوط به Heap sort را می بینید:

int *arr : آرایه ای است که قرار است مرتب شود.

int n : سر حد آرایه را نشان می دهد.

<br />
void heap_sort(int* arr, int n)<br />
{<br />
    make_max_heap(arr, n);<br />
    <br />
    int temp;<br />
    for (int i = n-1 ; i &gt; 0; i--)<br />
    {<br />
        temp = arr[0];<br />
        arr[0] = arr[i];<br />
        arr[i] = temp;<br />
        max_heapify(arr, i, 0);<br />
    }<br />
}<br />

و در آخر کدی کلی از مرتب سازی هرمی را همراه Main برنامه و یک مثال که به آن داده شده است را قرار می دهم:

درباره ی آریـان پــور

سلام . آریــان پور هستم . از نویسندگان میکروپـدیا .. علاقه مــند به برنامه نویسی و طراحی وب و شبکه ! دیدگاه ها و نظرات شما دوستان بررسی میشه و باعث دلگرمـی برای نوشتن مطالب بهتر و به روزتر . در تماس باشید با : aryanpour [at] micropedia [dot] ir با مـا همراه باشید ..

همچنین ببینید

کد B-Tree در جاوا

این برنامه ساده یک نمونه از ساختار BTree، را در زبان جاوا پیاده سازی می …

۶ دیدگاه ها

  1. آیا این الگوریتم برای سیستم های چند پردازنده ای کاربردی است؟

  2. پرینتر سه بعدی

    سلام

    الگوریتم های خود یادگیرنده رو هم میشه برامون بزارید؟

    تشکر

  3. سلام.ممنون از مطالبتون میخواستم که برنامه ای برای جارو برقی بنویسم در صورت امکان راهنمایی کنید.

  4. سلام سایت خوبی دارید با تشکر از سایت خوبتون واقعا عالیه!لطفا به سایت منم سری بزنید ارسال تبلیغات در وایبر به صورت رایگان و روزانه تا سقف۱۰٫۰۰۰٫۰۰۰عدد

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

پاسخ عبارت زیر را وارد کنید: *