اگر اوپن مایند را دنبال کرده باشید می دانید که می خواهیم تعدادی از الگوریتم های مرتب سازی معروف را بررسی کنیم . مرتب سازی هرمی یا Heap Sort یکی از بهترین روش های سورت کردن است که از مرتبه (o(n*log n است و از نظر کار آمدی در شبیه سازی حافظه بعد از Quick sort (مرتب سازی سریع) تقریبا بهترین عملکرد را دارد.
قبل از این که به ادامه بحث بپردازیم الگوریتم های مرتب سازی را که بررسی کرده ایم یا خواهیم کرد را بار دیگر معرفی می کنم :
-insertion sort
-merge sort
-Distribution sorts
– Concurrent sorts
– Heap sort
-Radix sort
این مرتب سازی بر اساس درخت Binary Heap است و به صورت بازگشتی پیاده سازی آن انجام می شود و کاربرد های زیادی دارد مخصوصا در طراحی صف های اولویت دار.
Max Binary Heap Tree – درخت دودویی هرمی :
درختMax Binary heap درختی است که تمام گره های آن حداکثر دو فرزند دارند و هر گره مقدارش بزرگ تر مساوی مقدار گره های فرزندش است .
در شکل زیر یک درخت 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)
{
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
int large = i;
if (left_child < n && arr[large] < arr[left_child])
{
large = left_child;
}
if (right_child < n && arr[large] < arr[right_child])
{
large = right_child;
}
if (large != i)
{
int temp;
temp = arr[i];
arr[i] = arr[large];
arr[large] = temp;
max_heapify(arr, n, large);
}
}
make_max_heap :
خوب حالا تابعی داریم که می تواند شرط درخت هیپ را برای یک گره برقرار کند . ما اگر این تابع را برای تمام گره ها از گره های برگ به ریشه فراخوانی کنیم در نتیجه آرایه تبدیل به یک درخت هیپ می شود که شرط بزرگ تر بودن مقدار پدر از فرزندان برای تمام گره ها برقرار می شود که این همام کاری است که تابع make_max_heap انجام می دهد که کد آن را در زیر می بینید:
void make_max_heap(int* arr, int n)
{
for (int i = n / 2 + 1; i >= 0; i--)
{
max_heapify(arr, n, i);
}
}
اگر به کد بالا توجه کنید می بینید ما از خانه ی n/2 آرایه شروع به فراخوانی تابع max_heapify کرده ایم تا به خانه ی صفر آرایه رسیدم از این کار دو هدف داشته ایم:
یک – اگر از خانه ی صفر شروع به فراخوانی تابع max_heapify می کردیم هر بار که آن تابع را فراخوانی می کردیم ممکن بود وضعیت گره ها در پایین عوض شود در نتیجه باید بارها از اول تا آخر این کار را برای تمام خانه های آرایه می کردیم تا آرایه به صورت هیپ در آید ولی وقتی از خانه ی آخر به خانه صفرم این کار را می کنیم دیگر این مشکل پیش نمی آید.
دو – شاید این سوال برای شما پیش آمده باشد چرا از خانه ی n/2 شروع کردیم و از n نکردیم ، به خاطر این که خانه های n/2 +1 به بعد برگ هستند و فرزندی ندارند که نگران آن باشیم که شرط هیپ برای آن ها برقرار نباشد.
خوب تا اینجا که آمدیم ما یه آرایه را گرفتیم و آن را به صورت درخت Max Heap در آوردیم حالا چطور از این آرایه استفاده کنیم و آرایه مرتب شده را به دست بیاوریم؟
اگر یادتان باشد در بالا گفتیم که یکی از مهمترین ویژگی آرایه ی به وجود آمده این است که خانه صفرم آرایه بزرگ ترین مقدار را در تمام آرایه دارد و ما از همین ویژگی استفاده می کنیم.
تابع heap_sort :
برای سورت با روش هرمی ابتدا خانه ی صفرم را بر می داریم و جای آن را با خانه ی آخر عوض می کنیم و یکی از سایز آرایه کم می کنیم ، در آرایه با ساختار هیپ بیشترین مقدار در خانه ی صفرم قرار دارد در نتیجه بزرگ ترین مقدار را از آرایه جدا کردیم ، با انتقال خانه ی آخر به خانه صفرم ساختار هیپ بهم می ریزد که با فراخوانی تابع
max_heapify بر روی خانه ی صفرم دوباره آرایه را به ساختار درخت هیپ تبدیل می کنیم ، در نتیجه دوباره بیشترین مقدار در خانه ی اول قرار می گیرد و دوباره همه ی این کار ها را تکرار می کنیم تا تمام اعضای آرایه را جدا کنیم و آرایه مرتب شده به صورت صعودی را به دست آوریم این پروسه در عکس زیر نشان داده شده است :
(عکس را از کتاب CLRS گرفتم)
در زیر کد مربوط به Heap sort را می بینید:
int *arr : آرایه ای است که قرار است مرتب شود.
int n : سر حد آرایه را نشان می دهد.
//Heap Sort
void heap_sort(int* arr, int n)
{
make_max_heap(arr, n);
int temp;
for (int i = n-1 ; i > 0; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
max_heapify(arr, i, 0);
}
}
و در آخر کدی کلی از مرتب سازی هرمی را همراه Main برنامه و یک مثال که به آن داده شده است را قرار می دهم :
// Heapsort(with Array).cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
//
void max_heapify(int*arr,int n,int i)
{
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
int large = i;
if (left_child < n && arr[large] < arr[left_child])
{
large = left_child;
}
if (right_child < n && arr[large] < arr[right_child])
{
large = right_child;
}
if (large != i)
{
int temp;
temp = arr[i];
arr[i] = arr[large];
arr[large] = temp;
max_heapify(arr, n, large);
}
}
//
void make_max_heap(int* arr, int n)
{
for (int i = n / 2 + 1; i >= 0; i--)
{
max_heapify(arr, n, i);
}
}
//Heap Sort
void heap_sort(int* arr, int n)
{
make_max_heap(arr, n);
int temp;
for (int i = n-1 ; i > 0; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
max_heapify(arr, i, 0);
}
}
int main( )
{
int *a = new int[6];
a[0] = 8;
a[1] = 7;
a[2] = 9;
a[3] = 2;
a[4] = 5;
a[5] = -1;
heap_sort(a, 6);
for (int i = 0; i < 6; i++)
{
cout << a[i] << " ,";
}
cout << endl;
return 0;
}
