-
Notifications
You must be signed in to change notification settings - Fork 73
Expand file tree
/
Copy pathHeapSort.java
More file actions
60 lines (51 loc) · 1.27 KB
/
HeapSort.java
File metadata and controls
60 lines (51 loc) · 1.27 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
package algorithm.basic;
/**
* A simple implementation of heap sort.
*
* @param <T> The comparable elements in heap.
*/
public class HeapSort<T extends Comparable<T>> {
private int heapSize;
public HeapSort() {
this.heapSize = 0;
}
public void heapSort(T[] arr) {
buildMaxHeap(arr);
for(int i = arr.length - 1; i >= 1; --i) {
T tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
--this.heapSize;
heapify(arr, 0);
}
}
private void heapify(T[] arr, int i) {
int largestIdx = i;
int leftChildIdx = leftChild(i);
if(leftChildIdx < heapSize && arr[leftChildIdx].compareTo(arr[largestIdx]) > 0) {
largestIdx =leftChildIdx;
}
int rightChildIdx = rightChild(i);
if(rightChildIdx < heapSize && arr[rightChildIdx].compareTo(arr[largestIdx]) > 0) {
largestIdx = rightChildIdx;
}
if(largestIdx != i) {
T tmp = arr[i];
arr[i] = arr[largestIdx];
arr[largestIdx] = tmp;
heapify(arr, largestIdx);
}
}
private void buildMaxHeap(T[] arr) {
this.heapSize = arr.length;
for(int i = arr.length / 2 - 1; i >= 0; --i) {
heapify(arr, i);
}
}
private int leftChild(int i) {
return i * 2 + 1;
}
private int rightChild(int i) {
return i * 2 + 2;
}
}