FilesExpand file tree

 master

/

HeapSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (44 loc) · 1.08 KB

 master

/

HeapSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (44 loc) · 1.08 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

/**

* Created by antrix190 on 22/10/2017

*/

public class HeapSort {

/*

* HeapSort is a comparison based sorting algorithms that uses a binary heap data structure. Its run time

* complexity is O(nlogn).

* */

public void sort(int arr[]){

int n = arr.length;

//Create heap

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

heapify(arr, n, i);

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

//Moving current root to the end.

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

//call Max heapify on the remaining heap.

heapify(arr, i, 0);

}

}

void heapify(int arr[], int n, int i){

//init

int largest = i;

int l = 2*i + 1;

int r = 2*i + 2;

//if left child is larger than root, largest =left.

if (l < n && arr[l] > arr[largest])

largest = l;

//if right child is larger than largest, largest =right

if (r < n && arr[r] > arr[largest])

largest = r;

//if largest is not root.

if (largest != i){

//rearrange the heap.

int swap = arr[i];

arr[i] = arr[largest];

arr[largest] = swap;

//Recursively heapify.

heapify(arr, n, largest);

}

}

}