K阵列中的最大元素复杂度

Question

我使用最大堆来查找数组中的k个最大元素，如下所示：

1） 我已经构建了给定数组的前k个元素（arr[0]到arr[k-1]）的最小堆MH。O（k）

2）对于每个元素，在第k个元素（arr[k]到arr[n-1]）之后，将其与MH的根进行比较。

……a）如果元素大于根，则将其设为根，并为MH调用heapify

……b）否则忽略它。

//步骤2是O（（n-k））

3）最后，MH有k个最大元素，MH的根是第k个最大元素。

我已经在网上搜索过了，第二步的复杂性显示了O（n-k）logk，我认为如果我们使用自底向上方法构建堆，它应该是（n-k）*O（k）。因为在每一步，只要找到一个更大的元素，我都会替换根。对k个元素的数组进行重分类的复杂度为O（k）

我错了吗？请澄清。我只是想知道我的想法是否正确？

我的方法如下：

private static void createMinHeap(int[] arr) {

        for (int i = arr.length / 2; i >= 0; i--) {
            restoreDown(arr, i);
        }

    }

    private static void restoreDown(int[] arr, int i) {

        int left = (2 * i) + 1;
        int right = (2 * i) + 2;
        int num = arr[i];

        while (right <= arr.length) {

            if (num <= arr[right] && num <= arr[left]) {
                arr[i] = num;
                return;
            } else if (arr[right] < arr[left]) {
                arr[i] = arr[right];
                i = right;
            } else {
                arr[i] = arr[left];
                i = left;
            }

            left = (2 * i) + 1;
            right = (2 * i) + 2;
        }

        if (left == arr.length - 1 && arr[left] < num) {
            arr[i] = arr[left];
            i = left;
        }

        arr[i] = num;

    }

Answer 1

选择算法允许您在O（n）时间内找到数组中的第k个元素或第k个最大元素。

Answer 2

您的推理几乎正确，但是对于大小为k的堆，heapify操作需要O（log k）。因此，总复杂度为O（n log k）。为什么？在最坏的情况下，您应该为剩余的每个元素执行heapify。由于k是固定的，并且n可以任意大，即O（n）步长，最后得出O（n log k）。

另请参见：

• 堆排序