array-heap-tree

الگوریتم های مرتب سازی: مرتب سازی هرمی (Heap-Sort)

array-heap-tree

اگر اوپن مایند را دنبال کرده باشید می دانید که می خواهیم تعدادی از الگوریتم های مرتب سازی معروف را بررسی کنیم . مرتب سازی هرمی یا  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 درختی است که تمام گره های آن  حداکثر دو فرزند دارند و هر گره مقدارش بزرگ تر مساوی مقدار گره های فرزندش است .

در شکل زیر یک درخت Max Binary heap را با جزییاتش می بینید :

Heap tree

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

ریشه را همیشه در خانه ی اول آرایه می گذاریم و فرزندان  گره ای i ام را در خانه ی ۲i+1 و ۲i+2 قرار می گیرد در نتیجه اگر درخت بالا را در آرایه قرار دهیم به شکل زیر می شود:

array-heap-tree

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

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

max_heapify :

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

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

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

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

make_max_heap :

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

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

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

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

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

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

تابع heap_sort :

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

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

2DSC_12801

(عکس را از کتاب CLRS گرفتم)

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

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

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

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

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۱۰ دیدگاه

پاسخ دهید

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