ミニヒープはどのように作成されますか？

Question

コードでは、文字列のストリームが与えられており、ストリーム中のk個の最長文字列を返しています。私の質問は、コンパレータはどのように機能するのですか？私は、無名関数を使って2つの文字列の長さを比較するcompareメソッドをオーバーライドすることを理解していますが、この比較によってどのようにminヒープが作成されますか？

public static List<String> topK(int k, Iterator<String> iter) { 
PriorityQueue<String> minHeap = new PriorityQueue<>(k, new Comparator<String>() { 
    public int compare(String s1, String s2) { 
    return Integer.compare(s1.length(), s2.length()); 
    } 
}); 
while (iter.hasNext()) { 
    minHeap.add(iter.next()); 
    if (minHeap.size() > k) { 
    // Remove the shortest string. Note that the comparison function above 
    // will order the strings by length. 
    minHeap.poll(); 
    } 
} 
return new ArrayList<>(minHeap); 
} 

Answer 1

：

このキューの先頭には、指定された順序に関して、少なくとも要素です。

そしてPriorityQueue.poll()：

キューの先頭を取得および削除、またはキューが空の場合はnullを返します。

コンパレータは長さを増やして要素をソートします。したがって、キューの先頭は最小の長さのものです。そのため、poll()を呼び出すと、最短の文字列がキューから削除されます。

最大でk個のアイテムをキューに保持するようにポップアップすると、これまでのところイテレータから取得されたアイテムの中で最も長いアイテムがkになります。イテレータが使い尽くされると、それらは（最大で）k最長のアイテムになります。

Answer 2

簡単な言葉で要約しようと

バイナリヒープは、バイナリキューの背後にある木のデータ構造の特殊なタイプです。ヒープでは、各ノードとその子ノードはいくつかの共通のパターンに従います。たとえば、最小ヒープでは、すべての子ノードが親ノードよりも大きくなければなりません。その結果、ルートノードには最小の番号が保持されます。

ヒープに変更（挿入、削除、更新）がある場合、ヒープは、共通の原則が維持されるように再構成されます（たとえば、その子供よりも小さい）。したがって、ヒープに対して何らかの操作が行われると、heapify操作が呼び出されます。したがって、最小ヒープの場合、最小ヒープサイズが呼び出されて原則が維持されます。したがって、min-heapify操作では、親ノードを子ノードと再帰的に比較して、どちらが低い値であるかをチェックし、値が小さい場合は親ノードとスワップされます。

これで、heapify操作のこの比較メソッドを実装しています。したがって、最大ヒープの場合は、逆の処理（親としてより高い値を設定）を実行します。また、独自の必要性を満たすことによって、カスタム比較メソッドを実装できます。

詳細については、バイナリヒープを使用して検索することができます。豊富なリソースがあります。 Javadoc of PriorityQueueから