ヒープを使用したKth最小の時間複雑度

Question

以下は、ヒープを使用して配列のk番目に小さい要素を見つけるためのコードです。時間の複雑さはO（n log（k））です。ここで、kはヒープのサイズです。

私が理解しているように、まず配列全体、つまりO（n）を調べてヒープを作成します。配列の最後に到達すると、ヒープの最上部にk番目の最小要素があり、最終的な答えとして即座に返すことができます。

ただし、以下のコードでは、kから配列の長さまでの追加ループがあります。私はこの2番目のループの必要性を本当に理解していません。

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個の要素を挿入する必要がある最初のループで。

現在、smallestK.peek（）は現在の最小のKを保持します。

2番目のループでは、配列の残りの要素を処理します。この値と現在の最小値Kを比較します。