本文共 3661 字，大约阅读时间需要 12 分钟。

topK������������������

1. topK���������K������������������

���������������������������������������������������������topK������������������������������K���������������������������K���������������������������������

���������������������������������������O(n log K)���������������������O(K)������������������������topK���������

2. ������K������������

������������������������������������������������������K���������������������������������

������������������������������������������O(n log K)���������������������O(K)���������������������������������k-th smallest������������������

3. ���������

���������������������������������������������������������������������������������������������������������O(n log n)���������������������������

���������������������������������������������������O(n log n)���������n���������������������������������������������������������������������O(log n)���������������������n������������

������������������������������������������������������O(1)���������������������������������

������������

public class HeapSortDemo {
    public static void heapSort(int[] array) {
        int n = array.length;
        // 1. ���������������
        for (int i = n - 1; i > 1; i--) {
            adjustdown(array, i, n);
        }
        int end = n - 1;
        while (end > 0) {
            // 2. ������
            int temp = array[0];
            array[0] = array[end];
            array[end] = temp;
            // 3. ���������
            adjustdown(array, 0, end);
            end--;
        }
    }
    private static void adjustdown(int[] array, int parent, int len) {
        int child = 2 * parent + 1;
        // ���������������������������
        while (child < len && (array[child] < array[child + 1])) {
            child++;
        }
        // ���������������������������������������
        while (child < len) {
            // ���������������������������������������
            if (array[child] > array[parent]) {
                // ������������������
                int temp = array[child];
                array[child] = array[parent];
                array[parent] = temp;
                // ������������������������������
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
}

���������������������������������������������������������������������������������������������������������������