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