مرتب سازی هرمی (Heap Sort) — به زبان ساده

۳۸۲۴ بازدید
آخرین به‌روزرسانی: ۱۹ شهریور ۱۴۰۲
زمان مطالعه: ۹ دقیقه
مرتب سازی هرمی (Heap Sort) — به زبان ساده

«مرتب سازی هرمی» (Heap Sort) یک الگوریتم مبتنی بر ساختار داده «هرم دودویی» (Binary Heap) است. این الگوریتم مرتب‌سازی، مشابه با مرتب‌سازی انتخابی است که طی آن، عنصر بیشینه یافت می‌شود و در انتها قرار می‌گیرد. فرایند مشابهی برای دیگر عناصر باقی‌مانده نیز انجام می‌شود. در ادامه، این الگوریتم مرتب سازی آموزش داده شده و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

997696

هرم دودویی چیست؟

ابتدا باید مفهوم «درخت دودویی کامل» (Complete Binary Tree) تعریف شود. یک درخت دودویی کامل، نوعی از درخت دودویی است که در هر سطح از آن، به جز احتمالا سطح آخر، به طور کامل پر شده است و همه گره‌ها تا حد امکان در چپ درخت قرار می‌گیرند. هرم دودویی یک درخت دودویی کامل است که در آن، عناصر به ترتیب خاصی قرار می‌گیرند که براساس آن گره والد بزرگ‌تر (یا کوچک‌تر) از مقادیر موجود در دو گره فرزند خودش است. حالتی که والد از فرزند خود بزرگ‌تر باشد را «هرم بیشینه» (Max Heap) و حالتی که والد از فرزند خود کوچک‌تر باشد را «هرم کمینه» (Min Heap) می‌نامند.

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

با توجه به اینکه هرم دودویی یک درخت دودویی کامل محسوب می‌شود، می‌توان آن را به سادگی به عنوان یک آرایه نمایش داد. شایان توجه است که نمایش مبتنی بر آرایه، کارایی فضایی دارد. اگر گره والد در اندیس I ذخیره شده باشد، فرزند چپ را می‌توان با 2I+12 * I + 1 و فرزند راست را با 2I+22 * I + 2 محاسبه کرد (با در نظر داشتن این فرض که اندیس‌ها از صفر شروع می‌شوند).

الگوریتم مرتب سازی هرمی برای مرتب‌سازی صعودی

  1. هرم بیشینه را از داده‌های ورودی بساز.
  2. در این نقطه، بزرگ‌ترین عنصر در ریشه هرم قرار دارد. آن را با آخرین عنصر هرم جایگزین و سایز هرم را یکی کاهش بده. در نهایت، ریشه درخت را هرمی کن.
  3. گام‌های بالا را تا هنگامی که اندازه هرم بزرگ‌تر از ۱ است ادامه بده.

روش ساخت هرم

روال هرمی‌سازی را می‌توان تنها هنگامی به یک گره اعمال کرد که گره‌های فرزند آن هرمی‌سازی شده باشند. بنابراین، هرمی‌سازی باید به صورت «پایین به بالا» (Bottom Up) انجام شود. برای درک بهتر این مبحث، در ادامه یک مثال ارائه شده است.

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

.عدد موجود در پرانتز نشان‌گر اندیس در نمایش آرایه‌ای داده‌ها است

:اعمال فرایند هرمی‌سازی به اندیس ۱
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

:اعمال فرایند هرمی‌سازی به اندیس صفر
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)
.روال هرمی‌سازی خودش را به طور بازگشتی فراخوانی می‌کند تا یک هرم را به صورت بالا به پایین بسازد

مرتب سازی هرمی در C

1// C implementation of Heap Sort
2#include <stdio.h>
3#include <stdlib.h>
4
5// A heap has current size and array of elements
6struct MaxHeap
7{
8    int size;
9    int* array;
10};
11
12// A utility function to swap to integers
13void swap(int* a, int* b) { int t = *a; *a = *b;  *b = t; }
14
15// The main function to heapify a Max Heap. The function
16// assumes that everything under given root (element at
17// index idx) is already heapified
18void maxHeapify(struct MaxHeap* maxHeap, int idx)
19{
20    int largest = idx;  // Initialize largest as root
21    int left = (idx << 1) + 1;  // left = 2*idx + 1
22    int right = (idx + 1) << 1; // right = 2*idx + 2
23
24    // See if left child of root exists and is greater than
25    // root
26    if (left < maxHeap->size &&
27        maxHeap->array[left] > maxHeap->array[largest])
28        largest = left;
29
30    // See if right child of root exists and is greater than
31    // the largest so far
32    if (right < maxHeap->size &&
33        maxHeap->array[right] > maxHeap->array[largest])
34        largest = right;
35
36    // Change root, if needed
37    if (largest != idx)
38    {
39        swap(&maxHeap->array[largest], &maxHeap->array[idx]);
40        maxHeapify(maxHeap, largest);
41    }
42}
43
44// A utility function to create a max heap of given capacity
45struct MaxHeap* createAndBuildHeap(int *array, int size)
46{
47    int i;
48    struct MaxHeap* maxHeap =
49              (struct MaxHeap*) malloc(sizeof(struct MaxHeap));
50    maxHeap->size = size;   // initialize size of heap
51    maxHeap->array = array; // Assign address of first element of array
52
53    // Start from bottommost and rightmost internal mode and heapify all
54    // internal modes in bottom up way
55    for (i = (maxHeap->size - 2) / 2; i >= 0; --i)
56        maxHeapify(maxHeap, i);
57    return maxHeap;
58}
59
60// The main function to sort an array of given size
61void heapSort(int* array, int size)
62{
63    // Build a heap from the input data.
64    struct MaxHeap* maxHeap = createAndBuildHeap(array, size);
65
66    // Repeat following steps while heap size is greater than 1.
67    // The last element in max heap will be the minimum element
68    while (maxHeap->size > 1)
69    {
70        // The largest item in Heap is stored at the root. Replace
71        // it with the last item of the heap followed by reducing the
72        // size of heap by 1.
73        swap(&maxHeap->array[0], &maxHeap->array[maxHeap->size - 1]);
74        --maxHeap->size;  // Reduce heap size
75
76        // Finally, heapify the root of tree.
77        maxHeapify(maxHeap, 0);
78    }
79}
80
81// A utility function to print a given array of given size
82void printArray(int* arr, int size)
83{
84    int i;
85    for (i = 0; i < size; ++i)
86        printf("%d ", arr[i]);
87}
88
89/* Driver program to test above functions */
90int main()
91{
92    int arr[] = {12, 11, 13, 5, 6, 7};
93    int size = sizeof(arr)/sizeof(arr[0]);
94
95    heapSort(arr, size);
96
97    printf("\nSorted array is \n");
98    printArray(arr, size);
99    return 0;
100}
101

مرتب سازی هرمی در ++C

1// C++ program for implementation of Heap Sort 
2#include <iostream> 
3  
4using namespace std; 
5  
6// To heapify a subtree rooted with node i which is 
7// an index in arr[]. n is size of heap 
8void heapify(int arr[], int n, int i) 
9{ 
10    int largest = i; // Initialize largest as root 
11    int l = 2*i + 1; // left = 2*i + 1 
12    int r = 2*i + 2; // right = 2*i + 2 
13  
14    // If left child is larger than root 
15    if (l < n && arr[l] > arr[largest]) 
16        largest = l; 
17  
18    // If right child is larger than largest so far 
19    if (r < n && arr[r] > arr[largest]) 
20        largest = r; 
21  
22    // If largest is not root 
23    if (largest != i) 
24    { 
25        swap(arr[i], arr[largest]); 
26  
27        // Recursively heapify the affected sub-tree 
28        heapify(arr, n, largest); 
29    } 
30} 
31  
32// main function to do heap sort 
33void heapSort(int arr[], int n) 
34{ 
35    // Build heap (rearrange array) 
36    for (int i = n / 2 - 1; i >= 0; i--) 
37        heapify(arr, n, i); 
38  
39    // One by one extract an element from heap 
40    for (int i=n-1; i>=0; i--) 
41    { 
42        // Move current root to end 
43        swap(arr[0], arr[i]); 
44  
45        // call max heapify on the reduced heap 
46        heapify(arr, i, 0); 
47    } 
48} 
49  
50/* A utility function to print array of size n */
51void printArray(int arr[], int n) 
52{ 
53    for (int i=0; i<n; ++i) 
54        cout << arr[i] << " "; 
55    cout << "\n"; 
56} 
57  
58// Driver program 
59int main() 
60{ 
61    int arr[] = {12, 11, 13, 5, 6, 7}; 
62    int n = sizeof(arr)/sizeof(arr[0]); 
63  
64    heapSort(arr, n); 
65  
66    cout << "Sorted array is \n"; 
67    printArray(arr, n); 
68} 

مرتب سازی هرمی در جاوا

1// Java program for implementation of Heap Sort 
2public class HeapSort 
3{ 
4    public void sort(int arr[]) 
5    { 
6        int n = arr.length; 
7  
8        // Build heap (rearrange array) 
9        for (int i = n / 2 - 1; i >= 0; i--) 
10            heapify(arr, n, i); 
11  
12        // One by one extract an element from heap 
13        for (int i=n-1; i>=0; i--) 
14        { 
15            // Move current root to end 
16            int temp = arr[0]; 
17            arr[0] = arr[i]; 
18            arr[i] = temp; 
19  
20            // call max heapify on the reduced heap 
21            heapify(arr, i, 0); 
22        } 
23    } 
24  
25    // To heapify a subtree rooted with node i which is 
26    // an index in arr[]. n is size of heap 
27    void heapify(int arr[], int n, int i) 
28    { 
29        int largest = i; // Initialize largest as root 
30        int l = 2*i + 1; // left = 2*i + 1 
31        int r = 2*i + 2; // right = 2*i + 2 
32  
33        // If left child is larger than root 
34        if (l < n && arr[l] > arr[largest]) 
35            largest = l; 
36  
37        // If right child is larger than largest so far 
38        if (r < n && arr[r] > arr[largest]) 
39            largest = r; 
40  
41        // If largest is not root 
42        if (largest != i) 
43        { 
44            int swap = arr[i]; 
45            arr[i] = arr[largest]; 
46            arr[largest] = swap; 
47  
48            // Recursively heapify the affected sub-tree 
49            heapify(arr, n, largest); 
50        } 
51    } 
52  
53    /* A utility function to print array of size n */
54    static void printArray(int arr[]) 
55    { 
56        int n = arr.length; 
57        for (int i=0; i<n; ++i) 
58            System.out.print(arr[i]+" "); 
59        System.out.println(); 
60    } 
61  
62    // Driver program 
63    public static void main(String args[]) 
64    { 
65        int arr[] = {12, 11, 13, 5, 6, 7}; 
66        int n = arr.length; 
67  
68        HeapSort ob = new HeapSort(); 
69        ob.sort(arr); 
70  
71        System.out.println("Sorted array is"); 
72        printArray(arr); 
73    } 
74}

مرتب سازی هرمی در پایتون

1# Python program for implementation of heap Sort 
2  
3# To heapify subtree rooted at index i. 
4# n is size of heap 
5def heapify(arr, n, i): 
6    largest = i # Initialize largest as root 
7    l = 2 * i + 1     # left = 2*i + 1 
8    r = 2 * i + 2     # right = 2*i + 2 
9  
10    # See if left child of root exists and is 
11    # greater than root 
12    if l < n and arr[i] < arr[l]: 
13        largest = l 
14  
15    # See if right child of root exists and is 
16    # greater than root 
17    if r < n and arr[largest] < arr[r]: 
18        largest = r 
19  
20    # Change root, if needed 
21    if largest != i: 
22        arr[i],arr[largest] = arr[largest],arr[i] # swap 
23  
24        # Heapify the root. 
25        heapify(arr, n, largest) 
26  
27# The main function to sort an array of given size 
28def heapSort(arr): 
29    n = len(arr) 
30  
31    # Build a maxheap. 
32    for i in range(n, -1, -1): 
33        heapify(arr, n, i) 
34  
35    # One by one extract elements 
36    for i in range(n-1, 0, -1): 
37        arr[i], arr[0] = arr[0], arr[i] # swap 
38        heapify(arr, i, 0) 
39  
40# Driver code to test above 
41arr = [ 12, 11, 13, 5, 6, 7] 
42heapSort(arr) 
43n = len(arr) 
44print ("Sorted array is") 
45for i in range(n): 
46    print ("%d" %arr[i]), 
47# This code is contributed by Mohit Kumra

مرتب سازی هرمی در #C

1// C# program for implementation of Heap Sort 
2using System; 
3  
4public class HeapSort 
5{ 
6    public void sort(int[] arr) 
7    { 
8        int n = arr.Length; 
9  
10        // Build heap (rearrange array) 
11        for (int i = n / 2 - 1; i >= 0; i--) 
12            heapify(arr, n, i); 
13  
14        // One by one extract an element from heap 
15        for (int i=n-1; i>=0; i--) 
16        { 
17            // Move current root to end 
18            int temp = arr[0]; 
19            arr[0] = arr[i]; 
20            arr[i] = temp; 
21  
22            // call max heapify on the reduced heap 
23            heapify(arr, i, 0); 
24        } 
25    } 
26  
27    // To heapify a subtree rooted with node i which is 
28    // an index in arr[]. n is size of heap 
29    void heapify(int[] arr, int n, int i) 
30    { 
31        int largest = i; // Initialize largest as root 
32        int l = 2*i + 1; // left = 2*i + 1 
33        int r = 2*i + 2; // right = 2*i + 2 
34  
35        // If left child is larger than root 
36        if (l < n && arr[l] > arr[largest]) 
37            largest = l; 
38  
39        // If right child is larger than largest so far 
40        if (r < n && arr[r] > arr[largest]) 
41            largest = r; 
42  
43        // If largest is not root 
44        if (largest != i) 
45        { 
46            int swap = arr[i]; 
47            arr[i] = arr[largest]; 
48            arr[largest] = swap; 
49  
50            // Recursively heapify the affected sub-tree 
51            heapify(arr, n, largest); 
52        } 
53    } 
54  
55    /* A utility function to print array of size n */
56    static void printArray(int[] arr) 
57    { 
58        int n = arr.Length; 
59        for (int i=0; i<n; ++i) 
60            Console.Write(arr[i]+" "); 
61        Console.Read(); 
62    } 
63  
64    // Driver program 
65    public static void Main() 
66    { 
67        int[] arr = {12, 11, 13, 5, 6, 7}; 
68        int n = arr.Length; 
69  
70        HeapSort ob = new HeapSort(); 
71        ob.sort(arr); 
72  
73        Console.WriteLine("Sorted array is"); 
74        printArray(arr); 
75    } 
76} 
77  
78// This code is contributed  
79// by Akanksha Rai(Abby_akku)

مرتب سازی هرمی در PHP

1<?php 
2  
3// Php program for implementation of Heap Sort 
4  
5// To heapify a subtree rooted with node i which is 
6// an index in arr[]. n is size of heap 
7function heapify(&$arr, $n, $i) 
8{ 
9    $largest = $i; // Initialize largest as root 
10    $l = 2*$i + 1; // left = 2*i + 1 
11    $r = 2*$i + 2; // right = 2*i + 2 
12  
13    // If left child is larger than root 
14    if ($l < $n && $arr[$l] > $arr[$largest]) 
15        $largest = $l; 
16  
17    // If right child is larger than largest so far 
18    if ($r < $n && $arr[$r] > $arr[$largest]) 
19        $largest = $r; 
20  
21    // If largest is not root 
22    if ($largest != $i) 
23    { 
24        $swap = $arr[$i]; 
25        $arr[$i] = $arr[$largest]; 
26        $arr[$largest] = $swap; 
27  
28        // Recursively heapify the affected sub-tree 
29        heapify($arr, $n, $largest); 
30    } 
31} 
32  
33// main function to do heap sort 
34function heapSort(&$arr, $n) 
35{ 
36    // Build heap (rearrange array) 
37    for ($i = $n / 2 - 1; $i >= 0; $i--) 
38        heapify($arr, $n, $i); 
39  
40    // One by one extract an element from heap 
41    for ($i = $n-1; $i >= 0; $i--) 
42    { 
43        // Move current root to end 
44        $temp = $arr[0]; 
45            $arr[0] = $arr[$i]; 
46            $arr[$i] = $temp; 
47  
48        // call max heapify on the reduced heap 
49        heapify($arr, $i, 0); 
50    } 
51} 
52  
53/* A utility function to print array of size n */
54function printArray(&$arr, $n) 
55{ 
56    for ($i = 0; $i < $n; ++$i) 
57        echo ($arr[$i]." ") ;  
58          
59}  
60  
61// Driver program 
62    $arr = array(12, 11, 13, 5, 6, 7); 
63    $n = sizeof($arr)/sizeof($arr[0]); 
64  
65    heapSort($arr, $n); 
66  
67    echo 'Sorted array is ' . "\n"; 
68      
69    printArray($arr , $n); 
70  
71// This code is contributed by Shivi_Aggarwal 
72?>

مرتب‌سازی هرمی یک الگوریتم «در جا» یا «در محل» (In-Place Algorithm) است. پیاده‌سازی متداول این الگوریتم «پایدار» (Stable) نیست، اما می‌توان آن را پایدار کرد.

پیچیدگی زمانی هرمی‌سازی از درجه (O(Logn، پیچیدگی زمانی ()createAndBuildHeap از درجه (O(n و پیچیدگی زمانی کلی الگوریتم مرتب‌سازی هرمی از درجه (O(nLogn است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۲ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۴ دیدگاه برای «مرتب سازی هرمی (Heap Sort) — به زبان ساده»

ای کاش منبع مقاله هم ذکر میکردید چون کاملا ترجمه از لینک زیر هست

سلام، وقت شما بخیر؛

منابع تمامی مطالب در انتهای آن‌ها ذکر شده است، از همراهی شما با مجله فرادرس بسیار سپاسگزاریم.

سلام خسته نباشید مطالب مفید بود من دنبال یه اپلیکیشن یا نرم افزاری میگردم ک بتونم اسامی رو به صورت درخت باینری به صورت هرمی در اورد من بازاریابی شبکه ای کار میکنم و لازمه ک تعداد نفرات رو توی یه برنامه جا بدم دیگ از درختی کشیدن دستی با خودکار روی کاغذ خسته شدم میشه کمکم کنید

مطالبتون خیلی مفیدن خانوم حصارکی شما بهترین نویسنده فرادرس هستید

نظر شما چیست؟

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