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

شنبه ۱۱ آبان ۱۳۹۸
بازدید ۵,۰۶۵ نفر
سعید سیفی زاده
(23 امتیاز از 5 رای)
Loading...

تصویر heap-sort-algorithm_7330 الگوریتم مرتب سازی هرمی (Heap Sort)

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

الگوریتم مرتب سازی هرمی (Heap Sort)، یک تکنیک مرتب سازی بر اساس مقایسه مبتنی بر ساختار داده دودویی هیپ است. Heap Sort شبیه به الگوریتم مرتب سازی انتخابی است. در این الگوریتم ابتدا بزرگترین عنصر پیدا شده و در انتهای آرایه قرار می گیرد. همین روند برای باقی عناصر تکرار می شود تا آرایه به طور کامل مرتب شود.

تصویر heap-sort-algorithm_7330_1 الگوریتم مرتب سازی هرمی (Heap Sort)

باینری هیپ چیست؟

اجازه دهید اول درخت دودویی کامل (Complete Binary Tree) را تعریف کنیم. Complete Binary Tree یک درخت دودویی است که در آن همه گره ها به جز برگ ها دارای دو فرزند هستند. یک باینری هیپ، یک درخت دودویی کامل است که در آن آیتم ها با ترتیب خاصی ذخیره می شوند. به طوری که مقدار گره والد بیشتر (یا کمتر) از مقادیر موجود در گره فرزندان است. یک هیپ را می توان با استفاده از درخت دودویی یا آرایه نمایش داد.

نحوه ساخت Heap

روش هیپ سازی (Heapify) فقط می تواند بر روی گره ای اعمال شود که فرزندان آن Heapify شده باشند. بنابراین عملیات heapification باید از پایین به بالا انجام شود.

برای درک بهتر نمونه زیر را مشاهده کنید:

Input data: 4, 10, 3, 5, 1
         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)

The numbers in bracket represent the indices in the array
representation of data.
Applying heapify procedure to index 1:
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

Applying heapify procedure to index 0:
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)

The heapify procedure calls itself recursively to build heap
 in top down manner.

Input data: 4, 10, 3, 5, 1

4(0)

/ \

10(1) 3(2)

/ \

5(3) 1(4)

The numbers in bracket represent the indices in the array

representation of data.

Applying heapify procedure to index 1:

4(0)

/ \

10(1) 3(2)

/ \

5(3) 1(4)

Applying heapify procedure to index 0:

10(0)

/ \

5(1) 3(2)

/ \

4(3) 1(4)

The heapify procedure calls itself recursively to build heap

in top down manner.

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

// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = 2*i + 1; // left = 2*i + 1
    int r = 2*i + 2; // right = 2*i + 2
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // Move current root to end
        swap(arr[0], arr[i]);
        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}
// Driver program
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    cout << "Sorted array is \n";
    printArray(arr, n);
}

// C++ program for implementation of Heap Sort

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

int largest = i; // Initialize largest as root

int l = 2*i + 1; // left = 2*i + 1

int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])

largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])

largest = r;

// If largest is not root

if (largest != i)

{

swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

}

// main function to do heap sort

void heapSort(int arr[], int n)

{

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// One by one extract an element from heap

for (int i=n-1; i>=0; i--)

{

// Move current root to end

swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);

}

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

for (int i=0; i<n; ++i)

cout << arr[i] << " ";

cout << "\n";

}

// Driver program

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);

}

امتحان کنید

خروجی:

Sorted array is
5 6 7 11 12 13

1 2	Sorted array is 5 6 7 11 12 13

تغییر به حالت نزولی

برای تغییر به حالت نزولی کافیست در تابع heapify شرط if (l < n && arr[l] > arr[largest]) را به if (l < n && arr[l] < arr[largest]) و شرط if (r < n && arr[r] > arr[largest]) به if (r < n && arr[r] < arr[largest]) تغییر دهید.

نکات

پیچیدگی زمانی برابر است با O(nLogn).
این الگوریتم استفاده محدودی دارد، زیرا الگوریتم Merge Sort و الگوریتم Quick Sort روش های بهتری نسبت به الگوریتم Heap Sort هستند.

الگوریتم ها - مرتب سازی پایه ای الگوریتم ها - مرتب سازی سریع