-
Notifications
You must be signed in to change notification settings - Fork 47
/
HeapSort.java
118 lines (102 loc) · 2.85 KB
/
HeapSort.java
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
public class HeapSort {
/**
* the implement method of HeapSort
* @param data which prepare for sorting
*/
public static void heapSort(int[] data) {
//from the end index, build the Max-Heapify
int startIndex = getParentIndex(data.length - 1);
for(int i = startIndex; i >= 0; i--) {
maxHeapifyByIteration(data, data.length, i);
//or
//maxHeapifyByIteration(data, data.length, i);
}
//swap the head and end. then maintain the Max-Heapify
for (int i = data.length - 1; i > 0; i--) {
swap(data, 0, i);
maxHeapifyByIteration(data, i, 0);
//or
//maxHeapifyByIteration(data, i, 0);
}
}
/**
* build the Max-Heapify by recursion method
* @param data input data
* @param heapSize length of data
* @param index from the end index, build the Max-Heapify
*/
private static void maxHeapifyByRecursion(int[] data, int heapSize, int index) {
//get the left and right index
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
//get the max data's index
int largest = index;
if(left < heapSize && data[index] < data[left]) {
largest = left;
}
if(right < heapSize && data[largest] < data[right]) {
largest = right;
}
//swap the max data to parent node. and then maintain the Max-Heapify again
if(largest != index) {
swap(data, largest, index);
maxHeapifyByRecursion(data, heapSize, largest);
}
}
/**
* build the Max-Heapify by iteration method
* @param data input data
* @param heapSize length of data
* @param index from the end index, build the Max-Heapify
*/
private static void maxHeapifyByIteration(int[] data, int heapSize, int index) {
while(true) {
//get the left and right index
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
//get the max data's index
int largest = index;
if(left < heapSize && data[index] < data[left]) {
largest = left;
}
if(right < heapSize && data[largest] < data[right]) {
largest = right;
}
//swap the max data to parent node. and then maintain the Max-Heapify again
if(largest != index) {
swap(data, largest, index);
index = largest;
}
else {
break;
}
}
}
/**
* swap data[i] and data[j]
* @param data
* @param i
* @param j
*/
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static int getParentIndex(int current) {
return (current - 1) / 2;
}
private static int getChildLeftIndex(int current) {
return 2 * current + 1;
}
private static int getChildRightIndex(int current) {
return 2 * (current + 1);
}
public static void main(String[] args) {
int[] sort = new int[]{1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11};
heapSort(sort);
for (int i = 0; i < sort.length; i++) {
System.out.print(sort[i] + " ");
}
}
}