从大到小
public class MinHeapSortTest {
@Test
public void testQuickSort() {
// testSort(QuickSort::sort);
testSort(arr -> MinHeapSortTest.minHeapSort(arr));
}
public void testSort(Consumer consumer) {
int[] result = {1, 2, 3, 4, 5, 6, 7};
int[] input = {7, 6, 5, 4, 3, 2, 1};
testSort(consumer, input, result);
testSort(consumer, new int[]{1, 3, 2, 6, 5, 4, 7}, result);
testSort(consumer, new int[]{6, 5, 4, 1, 3, 2, 7}, result);
testSort(consumer, new int[]{1, 3, 6, 5, 4, 2, 7}, result);
testSort(consumer, new int[]{6, 5, 4, 7, 1, 3, 2}, result);
}
public void testSort(Consumer consumer, int[] input, int[] result) {
System.out.println("src = " + Arrays.toString(input));
consumer.accept(input);
// 验证结果
for (int i = 0; i < result.length; i++) {
Assert.assertEquals("\ninp = " + Arrays.toString(input) + "\nout = " + Arrays.toString(result), input[i], result[i]);
}
}
/***********************/
public static void minHeapSort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
minHeapDown(arr, i, arr.length);
}
for (int i = arr.length - 1; i > 0; i--) {
int tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
minHeapDown(arr, 0, i);
}
int r = arr.length - 1;
int l = 0;
while (l < r) {
int tmp = arr[r];
arr[r] = arr[l];
arr[l] = tmp;
r--;
l++;
}
}
public static void minHeapDown(int[] arr, int i, int len) {
int tmp = arr[i];
for (int k = 2 * i + 1; k < len; k = 2 * i + 1) {
if (k + 1 < len && arr[k + 1] <= arr[k]) {
k++;
}
if (tmp <= arr[k]) {
break;
}
arr[i] = arr[k];
i = k;
}
arr[i] = tmp;
}
}
从小到大
public class HeapSort {
@Test
public void testQuickSort() {
// testSort(QuickSort::sort);
testSort(arr -> HeapSort.heapSort1(arr));
}
public void testSort(Consumer consumer) {
int[] result = {1, 2, 3, 4, 5, 6, 7};
int[] input = {7, 6, 5, 4, 3, 2, 1};
testSort(consumer, input, result);
testSort(consumer, new int[]{1, 3, 2, 6, 5, 4, 7}, result);
testSort(consumer, new int[]{6, 5, 4, 1, 3, 2, 7}, result);
testSort(consumer, new int[]{1, 3, 6, 5, 4, 2, 7}, result);
testSort(consumer, new int[]{6, 5, 4, 7, 1, 3, 2}, result);
}
public void testSort(Consumer consumer, int[] input, int[] result) {
System.out.println("src = " + Arrays.toString(input));
consumer.accept(input);
// 验证结果
for (int i = 0; i < result.length; i++) {
Assert.assertEquals("\ninp = " + Arrays.toString(input) + "\nout = " + Arrays.toString(result), input[i], result[i]);
}
}
public static void heapSort1(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapDown1(arr, i, arr.length);
}
for (int j = arr.length - 1; j > 0; j--) {
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
heapDown1(arr, 0, j);
}
}
public static void heapDown1(int[] arr, int i, int len) {
int tmp = arr[i];
for (int k = 2 * i + 1; k < len; k = k * 2 + 1) {
if (k + 1 < len && arr[k + 1] >= arr[k]) {
k++;
}
if (tmp >= arr[k]) {
break;
}
arr[i] = arr[k];
i = k;
}
arr[i] = tmp;
}
}
topK算法也可以使用 快速排序算法 实现
public class HeapSortTopK {
@Test
public void testSort() {
testSort(arr -> HeapSortTopK.topK(arr, 3, Integer::compareTo));
}
@Test
public void testSort1() {
// 取最大的3个值
List result = HeapSortTopK.topK(Arrays.asList(new Integer[]{1, 3, 6, 5, 4, 2, 7}), 3, (o1, o2) -> o2 - o1);
System.out.println(result);
}
public void testSort(Function, List> function) {
Integer[] result = {1, 2, 3};
Integer[] input = {7, 6, 5, 4, 3, 2, 1};
testSort(function, input, result);
testSort(function, new Integer[]{1, 3, 2, 6, 5, 4, 7}, result);
testSort(function, new Integer[]{6, 5, 4, 1, 3, 2, 7}, result);
testSort(function, new Integer[]{1, 3, 6, 5, 4, 2, 7}, result);
testSort(function, new Integer[]{6, 5, 4, 7, 1, 3, 2}, result);
}
public void testSort(Function, List> function, Integer[] input, Integer[] result) {
System.out.println("src = " + Arrays.toString(input));
List returnResult = function.apply(Arrays.asList(input));
// 验证结果
Assert.assertTrue(returnResult.size() == result.length);
for (int i = 0; i < result.length; i++) {
Assert.assertEquals("\ninp = " + returnResult.toString() + "\nout = " + Arrays.toString(result), returnResult.get(i), result[i]);
}
}
// 取list中最小的topK
public static List topK(List list, int topK, Comparator comparator) {
int len = Math.min(topK, list.size());
T[] heap = (T[])new Object[len];
for (int i = 0; i < len; i++) {
heap[i] = list.get(i);
}
initHeap(heap, len, comparator);
for (int i = len; i < list.size(); i++) {
T t = list.get(i);
int compare = comparator.compare(heap[0], t);
if (compare > 0) {
heap[0] = t;
downHeap(heap, 0, len, comparator);
}
}
for (int i = len - 1; i > 0; i--) {
T tmp = heap[i];
heap[i] = heap[0];
heap[0] = tmp;
downHeap(heap, 0, i, comparator);
}
return Arrays.asList(heap);
}
public static void initHeap(T[] heap, int len, Comparator comparator) {
for (int i = len / 2 - 1; i >= 0; i--) {
downHeap(heap, i, len, comparator);
}
}
public static void downHeap(T[] heap, int i, int len, Comparator comparator) {
T tmp = heap[i];
for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
if (k + 1 < len && comparator.compare(heap[k], heap[k + 1]) <= 0) {
k++;
}
if (comparator.compare(tmp, heap[k]) >= 0) {
break;
}
heap[i] = heap[k];
i = k;
}
heap[i] = tmp;
}
}