FilesExpand file tree

 master

/

HeapSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

118 lines (100 loc) · 3.35 KB

 master

/

HeapSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

118 lines (100 loc) · 3.35 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

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

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import static Sorts.SortUtils.*;

/**

* Heap Sort Algorithm

* Implements MinHeap

*

* @author Kundan Kumar

*/

public class HeapSort implements SortAlgorithm {

private static class Heap<T extends Comparable<T>> {

/**

* Array to store heap

*/

private T[] heap;

/**

* Constructor

*

* @param heap array of unordered integers

*/

public Heap(T[] heap) {

this.heap = heap;

}

/**

* Heapifies subtree from top as root to last as last child

*/

private void heapSubtree(int rootIndex, int lastChild) {

int leftIndex = rootIndex * 2 + 1;

int rightIndex = rootIndex * 2 + 2;

T root = heap[rootIndex];

if (rightIndex <= lastChild) { // if has right and left children

T left = heap[leftIndex];

T right = heap[rightIndex];

if (less(left, right) && less(left, root)) {

swap(heap, leftIndex, rootIndex);

heapSubtree(leftIndex, lastChild);

} else if (less(right, root)) {

swap(heap, rightIndex, rootIndex);

heapSubtree(rightIndex, lastChild);

}

} else if (leftIndex <= lastChild) { // if no right child, but has left child

T left = heap[leftIndex];

if (less(left, root)) {

swap(heap, leftIndex, rootIndex);

heapSubtree(leftIndex, lastChild);

}

}

}

/**

* Makes heap with root as root

*/

private void makeMinHeap(int root) {

int leftIndex = root * 2 + 1;

int rightIndex = root * 2 + 2;

boolean hasLeftChild = leftIndex < heap.length;

boolean hasRightChild = rightIndex < heap.length;

if (hasRightChild) { //if has left and right

makeMinHeap(leftIndex);

makeMinHeap(rightIndex);

heapSubtree(root, heap.length - 1);

} else if (hasLeftChild) {

heapSubtree(root, heap.length - 1);

}

}

/**

* Gets the root of heap

*/

private T getRoot(int size) {

swap(heap, 0, size);

heapSubtree(0, size - 1);

return heap[size]; // return old root

}

}

@Override

public <T extends Comparable<T>> T[] sort(T[] unsorted) {

return sort(Arrays.asList(unsorted)).toArray(unsorted);

}

@Override

public <T extends Comparable<T>> List<T> sort(List<T> unsorted) {

int size = unsorted.size();

@SuppressWarnings("unchecked")

Heap<T> heap = new Heap<>(unsorted.toArray((T[]) new Comparable[unsorted.size()]));

heap.makeMinHeap(0); // make min heap using index 0 as root.

List<T> sorted = new ArrayList<>(size);

while (size > 0) {

T min = heap.getRoot(--size);

sorted.add(min);

}

return sorted;

}

/**

* Main method

*/

public static void main(String[] args) {

Integer[] heap = {4, 23, 6, 78, 1, 54, 231, 9, 12};

HeapSort heapSort = new HeapSort();

print(heapSort.sort(heap));

}

}