K largest elements in an array complexity

Question

I am using a max heap to find the k largest elements in an array as follows:

1) I have Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)

2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.

……a) If the element is greater than the root then make it root and call heapify for MH

……b) Else ignore it.

// The step 2 is O((n-k))

3) Finally, MH has k largest elements and root of the MH is the kth largest element.

I have searched over the net and the complexity for 2nd step is showing me O(n-k)logk which i think should be (n-k)*O(k) if we build the heap using bottom up approach.Because at every step i am just replacing the root whenever a greater element is found. And the complexity to heapify an array of k elements is O(k)

Am i wrong please clarify. I just need to know if i am thinking correct?

My method is as follows :

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

Your reasoning is almost correct, however with the heap of size k, heapify operation takes O(log k). Therefore, total complexity is O(n log k). Why? In the worst case, you should execute heapify for each of n-k remaining elements. Since k is fixed and n can be arbitrary large, that is O(n) steps, which finally gives O(n log k).

See also:

• Heap sort