FilesExpand file tree

 master

/

HeapSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (38 loc) · 1.18 KB

 master

/

HeapSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (38 loc) · 1.18 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

import java.util.Arrays;

class HeapSort{

public static void sortRecursive(int[] arr){

int len = arr.length;

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

heapify(arr, len, i);

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

int temp = arr[i];

arr[i] = arr[0];

arr[0] = temp;

heapify(arr, i, 0);

}

}

private static void heapify(int[] arr, int n, int rootIndex){

int largest = rootIndex; // Initializing root element as a largest

int left = 2*rootIndex + 1; // left element index in a heap

int right = 2*rootIndex + 2; // right element index in a heap

if(left < n && arr[left] > arr[largest]){

largest = left;

}

if(right < n && arr[right] > arr[largest]){

largest = right;

}

if(largest != rootIndex){

int temp = arr[rootIndex];

arr[rootIndex] = arr[largest];

arr[largest] = temp;

// recursively heapify the rest of the tree

heapify(arr, n, largest);

}

}

public static void main(String args[]){

int[] arr = {10,80,20,70,30,60,40,50,10};

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

HeapSort.sortRecursive(arr);

System.out.println("Sorted array using recursive heap sort: "+ Arrays.toString(arr));

}

}