forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.java
More file actions
68 lines (61 loc) · 1.65 KB
/
HeapSort.java
File metadata and controls
68 lines (61 loc) · 1.65 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
package com.dev.namhoai.sort;
public class HeapSort {
public void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
heapAdd(arr, i);
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i - 1);
}
}
private void heapify(int[] arr, int end) {
int i = 0;
int leftIndex;
int rightIndex;
while (i <= end) {
leftIndex = 2 * i + 1;
if (leftIndex > end) {
break;
}
rightIndex = 2 * i + 2;
if (rightIndex > end) {
rightIndex = leftIndex;
}
if (arr[i] >= Math.max(arr[leftIndex], arr[rightIndex])) {
break;
}
if (arr[leftIndex] >= arr[rightIndex]) {
swap(arr, i, leftIndex);
i = leftIndex;
} else {
swap(arr, i, rightIndex);
i = rightIndex;
}
}
}
private void swap(int[] arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
private void heapAdd(int[] arr, int end) {
int i = end;
while (i > 0) {
if (arr[i] > arr[(i - 1) / 2]) {
swap(arr, i, (i - 1) / 2);
i = (i - 1) / 2;
} else {
break;
}
}
}
public static void main(String[] args) {
HeapSort hs = new HeapSort();
int[] arr = {-1, 5, 8, 2, -6, -8, 11, 5};
hs.sort(arr);
for (int a : arr) {
System.out.println(a);
}
}
}