forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.java
More file actions
115 lines (98 loc) · 2.89 KB
/
Copy pathHeapSort.java
File metadata and controls
115 lines (98 loc) · 2.89 KB
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
package src.main.java.com.sorts;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static src.main.java.com.sorts.SortUtils.less;
import static src.main.java.com.sorts.SortUtils.swap;
public class HeapSort {
private static class Heap<T extends Comparable<T>> {
/**
* Array to store heap
*/
private T[] heap;
/**
* Constructor
*
* @param heap array of unordered integers
*/
Heap(T[] heap) {
this.heap = heap;
}
/**
* Heapifies subtree from top as root to last as last child
*
* @param rootIndex index of root
* @param lastChild index of 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
*
* @param root index of root of heap
*/
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
*
* @return root of heap
*/
private T getRoot(int size) {
swap(heap, 0, size);
heapSubtree(0, size - 1);
// return old root
return heap[size];
}
}
public <T extends Comparable<T>> T[] sort(T[] unsorted) {
return sort(Arrays.asList(unsorted)).toArray(unsorted);
}
private <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()]));
// make min heap using index 0 as root.
heap.makeMinHeap(0);
List<T> sorted = new ArrayList<>(size);
while (size > 0) {
T min = heap.getRoot(--size);
sorted.add(min);
}
return sorted;
}
}