-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
Heapsort.java
74 lines (61 loc) · 1.73 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
/**
* Implementation of heapsort
*
* <p>Run with:
*
* <p>$ ./gradlew run -Palgorithm=sorting.Heapsort
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.sorting;
import java.util.*;
public class Heapsort implements InplaceSort {
@Override
public void sort(int[] values) {
Heapsort.heapsort(values);
}
private static void heapsort(int[] ar) {
if (ar == null) return;
int n = ar.length;
// Heapify, converts array into binary heap O(n), see:
// http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
for (int i = Math.max(0, (n / 2) - 1); i >= 0; i--) {
sink(ar, n, i);
}
// Sorting bit
for (int i = n - 1; i >= 0; i--) {
swap(ar, 0, i);
sink(ar, i, 0);
}
}
private static void sink(int[] ar, int n, int i) {
while (true) {
int left = 2 * i + 1; // Left node
int right = 2 * i + 2; // Right node
int largest = i;
// Right child is larger than parent
if (right < n && ar[right] > ar[largest]) largest = right;
// Left child is larger than parent
if (left < n && ar[left] > ar[largest]) largest = left;
// Move down the tree following the largest node
if (largest != i) {
swap(ar, largest, i);
i = largest;
} else break;
}
}
private static void swap(int[] ar, int i, int j) {
int tmp = ar[i];
ar[i] = ar[j];
ar[j] = tmp;
}
/* TESTING */
public static void main(String[] args) {
Heapsort sorter = new Heapsort();
int[] array = {10, 4, 6, 4, 8, -13, 2, 3};
sorter.sort(array);
// Prints:
// [-13, 2, 3, 4, 4, 6, 8, 10]
System.out.println(java.util.Arrays.toString(array));
}
}