-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy pathHeapSort.java
More file actions
92 lines (84 loc) · 2.57 KB
/
HeapSort.java
File metadata and controls
92 lines (84 loc) · 2.57 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
package com.examplehub.sorts;
import com.examplehub.utils.SortUtils;
public class HeapSort implements Sort {
@Override
public void sort(int[] numbers) {
heapInsert(numbers);
int length = numbers.length;
while (length > 1) {
SortUtils.swap(numbers, 0, --length);
heapify(numbers, 0, length);
}
}
public void heapInsert(int[] numbers) {
for (int i = 0; i < numbers.length; ++i) {
int currentIndex = i;
int parentIndex = (currentIndex - 1) / 2;
while (numbers[currentIndex] > numbers[parentIndex]) {
SortUtils.swap(numbers, currentIndex, parentIndex);
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
}
}
}
public void heapify(int[] numbers, int index, int length) {
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
while (leftIndex < length) {
int maxIndex = index;
if (numbers[leftIndex] > numbers[maxIndex]) {
maxIndex = leftIndex;
}
if (rightIndex < length && numbers[rightIndex] > numbers[maxIndex]) {
maxIndex = rightIndex;
}
if (maxIndex == index) {
break;
}
SortUtils.swap(numbers, maxIndex, index);
index = maxIndex;
leftIndex = 2 * index + 1;
rightIndex = 2 * index + 2;
}
}
@Override
public <T extends Comparable<T>> void sort(T[] array) {
heapInsert(array);
int length = array.length;
while (length > 1) {
SortUtils.swap(array, 0, --length);
heapify(array, 0, length);
}
}
public <T extends Comparable<T>> void heapInsert(T[] numbers) {
for (int i = 0; i < numbers.length; ++i) {
int currentIndex = i;
int parentIndex = (currentIndex - 1) / 2;
while (numbers[currentIndex].compareTo(numbers[parentIndex]) > 0) {
SortUtils.swap(numbers, currentIndex, parentIndex);
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
}
}
}
public <T extends Comparable<T>> void heapify(T[] numbers, int index, int length) {
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
while (leftIndex < length) {
int maxIndex = index;
if (numbers[leftIndex].compareTo(numbers[maxIndex]) > 0) {
maxIndex = leftIndex;
}
if (rightIndex < length && numbers[rightIndex].compareTo(numbers[maxIndex]) > 0) {
maxIndex = rightIndex;
}
if (maxIndex == index) {
break;
}
SortUtils.swap(numbers, maxIndex, index);
index = maxIndex;
leftIndex = 2 * index + 1;
rightIndex = 2 * index + 2;
}
}
}