FilesExpand file tree

 master

/

HeapSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (55 loc) · 1.44 KB

 master

/

HeapSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (55 loc) · 1.44 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.Arrays;

import java.util.Scanner;

public class HeapSort {

public static void main(String args[]){

int size = 0, i=0;

Scanner in = new Scanner(System.in);

System.out.println("Enter size of the array");

size = in.nextInt();

int arr[] = new int[size];

for ( i = 0 ;i < size; i++ ){

arr[i] = in.nextInt();

}

System.out.println("Unsorted Array : "+Arrays.toString(arr));

heapSort(arr,arr.length);

System.out.println("Sorted Sequence : "+Arrays.toString(arr));

in.close();

}

public static void heapSort(int arr[],int len){

int i=0 ;

//To Create heap

for(i=len/2;i>=0;i--){

maxHeap(arr,i,len);

}

//To arrange the max heap

for( i = len-1 ; i>=0 ;i-- ){

int temp = arr[0];

arr[0]=arr[i];

arr[i]=temp;

//Max heap on reduced array size

maxHeap(arr,0,i);

}

}

public static void maxHeap( int a[],int largeIndex ,int len){

int max = largeIndex;

int left = 2*largeIndex;

System.out.println("Left : "+left);

int right = left + 1;

System.out.println("Right : "+right);

//If left is max than the current root element

if( left < len && a[max]<a[left]){

max = left;

}

//If left is max than the current root element

if( right < len && a[max]<a[right]){

max = right;

}

//Swap if the current node and passed node are different and recurse on maxheap.

if ( max != largeIndex ){

int temp = a[max];

a[max] = a[largeIndex];

a[largeIndex] = temp;

maxHeap(a, max, len);

}

}

}