Java_Programs/HeapSort.java at main · jvm-coder/Java_Programs · 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Scanner;

public class HeapSort {
    public static void heapify(int a[],int i,int n)
    {

        int l=2*i+1;
        int r=2*i+2;


        int temp,largest;

        if(l<n && a[l]>a[i])
            largest=l;
        else
            largest=i;

        if(r<n && a[r]>a[largest])
            largest=r;

        if(largest !=i)
        {
            temp=a[largest];
            a[largest]=a[i];
            a[i]=temp;

            heapify(a,largest,n);
        }


    }

    public static void bheap(int a[])
    {

        for(int i=(a.length/2)-1;i>=0;i--)
        {

            heapify(a,i,a.length);

        }

    }

    public static void Sort(int a[])
    {
        int temp,j,i;

        bheap(a);

        for( i=(a.length)-1; i>0;)
        {
            temp=a[0];
            a[0]=a[i];
            a[i]=temp;
            heapify(a,0,i--) ;

        }

    }

    public static void printarray(int a[])
    {
        System.out.println();
        for (int j : a) {

            System.out.print(j + " ");
        }

    }
    public static void main(String[] args)
    {
        int n, res,i;
        Scanner s = new Scanner(System.in);
        System.out.print("Enter number of elements in the array:");
        n = s.nextInt();
        int[] a = new int[n];
        System.out.println("Enter "+n+" elements ");
        for( i=0; i < n; i++)
        {
            a[i] = s.nextInt();
        }

        System.out.println( "elements in array ");
        printarray(a);
        Sort(a);
        System.out.println( "\nelements after sorting");
        printarray(a);

    }
}