JavaCode-Hacktoberfest2021/HeapSort.java at main · Krushna-Prasad-Sahoo/JavaCode-Hacktoberfest2021 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class HeapSort implements SortingStrategy{
 @Override
    public String sort(int[] inputArray) {
        int n = inputArray.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(inputArray, n, i);

        // One by one extract an element from heap
        for (int i=n-1; i>0; i--)
        {

            int temp = inputArray[0];
            inputArray[0] = inputArray[i];
            inputArray[i] = temp;


            heapify(inputArray, i, 0);
        }
     return null;

    }


    String heapify(int inputArray[], int n, int i)
    {
        int largest = i;
        int l = 2*i + 1;
        int r = 2*i + 2;

        // If left child is larger than root
        if (l < n && inputArray[l] > inputArray[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && inputArray[r] > inputArray[largest])
            largest = r;

        // If largest is not root
        if (largest != i)
        {
            int swap = inputArray[i];
            inputArray[i] = inputArray[largest];
            inputArray[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(inputArray, n, largest);
        }
    String list = "";
        for(int k:inputArray){
            list = list+i+" ";
        }
        return list;

    }
}