-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathCode_03_MinHeapSort.java
More file actions
179 lines (159 loc) · 5.12 KB
/
Code_03_MinHeapSort.java
File metadata and controls
179 lines (159 loc) · 5.12 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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
package algorithm.basic;
import java.util.Arrays;
import java.util.Comparator;
/**
* @Created by mood321
* @Date 2019/10/6 0006
* @Description 堆的操作 入堆 出堆 和堆 排序
*/
public class Code_03_MinHeapSort {
/**
* 堆排序 代码
*
* @param arr
*/
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 思路 : 1 把所有元素放在堆
// 2 依据堆的特性排序
// 复杂度 O(N*Log2(N)) 不稳定
for (int i = 0; i < arr.length; i++) { // 可以重用数组空间 节省额外空间 从1开始
heapInsert(arr, i);
}
// 出堆
// 每次出堆 堆大小-1 拿出元素放在数组里
for (int i = arr.length; i > 0; i--) {
heapify(arr, 0, i);
}
}
/**
* <p> 1.把需要入堆的元素放在 heapsize+1 位置（最后一个节点）
* <p> 2.去和父节点比较大小 如大顶堆 比父节点大就交换 （父节点index= (子节点index-1) /2） 然后继续比较
*
* @param arr
* @param index
*/
public static void heapInsert(int[] arr, int index) {
// 入堆 思路, 放在最后节点 向上冒 和父节点比
while (arr[index] < arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
/**
* 出堆 操作
* <p> 1.头结点和最后一个节点交换 交换后最后一个节点是需要弹出的值 堆大小-1
*
* <p> 2.继续堆化 此时顶点的数据 不一定是最大的 他需要和子节点大的比较 大于则不动 小于交换
* <p> ps:（此处不是和每个节点比较 因为堆只要求父节点大于子节点 不要求左节点小于右节点）
* <p> 3.交换后 继续2的操作
* 此方法只做2-3 ps: 可以做
*
* @param arr
* @param index
* @param size
*/
public static void heapify(int[] arr, int index, int size) {
// 先交换
swap(arr, index, --size);
int left = index * 2 + 1;
while (left < size) {
// 主题逻辑 左右大小 然后大的和父 谁小
int min = left + 1 < size && arr[left + 1] < arr[left] ? left + 1 : left; // 取子节点 谁小
min = arr[index] > arr[min] ? min : index;
if (index == min) {
break;
}
swap(arr, index, min);
index=min;
left=min*2+1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test
public static void comparator(Integer[] arr) {
Arrays.sort(arr,new MinComparator());
}
public static class MinComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static Integer[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
Integer[] res = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, Integer[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
Integer[] arr2 = copyArray(arr1);
heapSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
//arr =new int[] {5, 2, 8, 4, 1, 9, 16};
heapSort(arr);
printArray(arr);
}
}