Сложность времени Kth наименьшая с использованием кучи

Question

Ниже приведен код для нахождения k-го наименьшего элемента в массиве с использованием кучи. Сложность времени - O (n log (k)), где k - размер кучи.

Как я понимаю, сначала вы пройдете весь массив, то есть O (n), чтобы заполнить свою кучу. И когда вы достигнете конца массива, у вас будет k-й наименьший элемент в верхней части кучи, который вы можете мгновенно вернуть в качестве окончательного ответа.

Однако в приведенном ниже коде имеется дополнительный цикл, начинающийся от k до длины массива. Я не совсем понимаю необходимость этого второго цикла.

public int findKthSmallest(int[] arr, int k) { 

    if(k <= 0 || k > arr.length) { 
     throw new IllegalArgumentException(); 
    } 

    PriorityQueue<Integer> smallestK = new PriorityQueue<>(k, Collections.reverseOrder()); 

    for(int i = 0; i < arr.length; i++) { 
     smallestK.add(arr[i]); 
    } 

    for(int j = k; j < arr.length; j++) { 
     if(arr[j] < smallestK.peek()) { 
      smallestK.remove(); 
      smallestK.add(arr[j]); 
     } 
    } 
    return smallestK.peek(); 
} 

Answer 1

Вы читаете неправильный код, он должен быть:

for(int i = 0; i < k; i++) { 
    smallestK.add(arr[i]); 
} 

В первом цикле нам нужно вставить первый элемент K в куче.

В настоящий момент самый маленькийK.peek() будет удерживать текущий самый маленькийK.

Во втором цикле мы обрабатываем оставшийся элемент в массиве. Мы сравниваем значение с текущим наименьшим К.