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

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

الگوریتم مرتب سازی هرمی (Heap Sort)، یک تکنیک مرتب سازی بر اساس مقایسه مبتنی بر ساختار داده دودویی هیپ است. 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.

پیاده سازی الگوریتم مرتب سازی هرمی (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);
}

امتحان کنید

خروجی:

Sorted array is
5 6 7 11 12 13

نکات

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

نوشته الگوریتم مرتب سازی هرمی (Heap Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.