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

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

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

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)

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?>