1

最小ヒープは、その効率のためにクラスが使用する構造であることを理解しています。ソートされていないデータが PQ に渡されると、それがヒープにソートされるように思えます。

ただし、compareTo メソッドに従って昇順の要素が供給されると、PQ で最初のアクションが実行された後、それをヒープにソートするのを待ちます。

これがなぜなのか知っていますか？順序付けられていないデータの場合のように、自動的に並べ替えられない理由がわかりません。

私の問題を示していると思われるプログラムを添付しました。

出力：

ソートされていないデータ:

[A、B、D、C、L、F、E、J]

あ

[B、C、D、J、L、F、E]

[1、2、4、3、12、6、5、10]

1

[2、3、4、10、12、6、5]

ソートされたデータ:

[A、B、C、D、E、F、G、H]

あ

[B、D、C、H、E、F、G]

[1、2、3、4、5、6、7、8]

1

[2、4、3、8、5、6、7]

import java.util.PriorityQueue;

public class Queue2
{
    public static void main(String[] args)
    {
        PriorityQueue<String> pQueue = new PriorityQueue<String>();

        pQueue.add("A");
        pQueue.add("C");
        pQueue.add("F");
        pQueue.add("B");
        pQueue.add("L");
        pQueue.add("D");
        pQueue.add("E");
        pQueue.add("J");
        System.out.println(pQueue); 
        System.out.println(pQueue.remove());
        System.out.println(pQueue);

        System.out.println();

        PriorityQueue<Integer> pQueue2 = new PriorityQueue<Integer>();

        pQueue2.add(1);
        pQueue2.add(3);
        pQueue2.add(6);
        pQueue2.add(2);
        pQueue2.add(12);
        pQueue2.add(4);
        pQueue2.add(5);
        pQueue2.add(10);
        System.out.println(pQueue2); 
        System.out.println(pQueue2.remove());
        System.out.println(pQueue2);

        System.out.println();

        PriorityQueue<String> pQueue3 = new PriorityQueue<String>();

        pQueue3.add("A");
        pQueue3.add("B");
        pQueue3.add("C");
        pQueue3.add("D");
        pQueue3.add("E");
        pQueue3.add("F");
        pQueue3.add("G");
        pQueue3.add("H");
        System.out.println(pQueue3); 
        System.out.println(pQueue3.remove());
        System.out.println(pQueue3);

        System.out.println();

        PriorityQueue<Integer> pQueue4 = new PriorityQueue<Integer>();

        pQueue4.add(1);
        pQueue4.add(2);
        pQueue4.add(3);
        pQueue4.add(4);
        pQueue4.add(5);
        pQueue4.add(6);
        pQueue4.add(7);
        pQueue4.add(8);
        System.out.println(pQueue4); 
        System.out.println(pQueue4.remove());
        System.out.println(pQueue4);

    }
}
4

2 に答える 2

2

PriorityQueueのドキュメントから

このキューの先頭は、指定された順序に関して最小の要素です。複数の要素が最小値で結合されている場合、ヘッドはそれらの要素の 1 つです。結合は任意に解除されます。キューの取得操作は、キューの先頭にある要素にポーリング、削除、ピーク、および要素アクセスします。

と

このクラスとその反復子は、 Collection および Iterator インターフェースのすべてのオプション メソッドを実装します。メソッド iterator() で提供される Iterator は、優先キューの要素を特定の順序でトラバースすることは保証されていません。順序付けされたトラバーサルが必要な場合は、Arrays.sort(pq.toArray()) の使用を検討してください。

poll()そのため、( System.outを使用して) キューを内部的に出力するときに反復子が使用されるため、並べ替えられた出力の保証はありません。

于 2013-05-28T14:58:28.727 に答える
0

キューの基礎となる (バイナリ) ヒープがあることをご存知ですか? ヒープは次の 2 つのプロパティに従う必要があります。

  • shape プロパティ:ツリーは完全なバイナリ ツリーです。つまり、最後のレベル (最も深いレベル) を除いて、ツリーのすべてのレベルが完全に埋められ、ツリーの最後のレベルが完全でない場合は、そのレベルのノードが左から右に埋められます。
  • ヒープ プロパティ: 各ノードは、データ構造に対して定義された比較述語に従って、その子のそれぞれ以上です。

では、要素はどのように挿入されるのでしょうか。空の場所に到達するまで BFS を実行する (その場所に要素を配置する) か、現在の要素よりも大きな別の要素を見つける (その要素を新しい要素に置き換えて、より大きな要素を続行します)。

2 つの例を見てみましょう。レベルごとにツリーを記述します。つまり、ルートとして を[A][BC][D---]持つツリー、およびの子、およびの子を意味します。ABCADB

最初の例を見てみましょう: [A, C, F, B, L, D, E, J]. これはヒープがどのように成長するかです:

[A]
[A][C-]
[A][CF]
[A][BF][C---]
[A][BF][CL--]
[A][BD][CLF-]
[A][BD][CLFE]
[A][BD][CLFE][J-------]

次に、ソートされた例を見てください: [A, B, C, D, E, F, G, H]. これは、そのヒープがどのように成長するかです:

[A]
[A][B-]
[A][BC]
[A][BC][D---]
[A][BC][DE--]
[A][BC][DEF-]
[A][BC][DEFG]
[A][BC][DEFG][H-------]

実際、基になる配列にはすべての要素がソートされた順序で含まれています。

では、最初の要素が削除されると、なぜこの順序が歪むのでしょうか? 両方のヒープ プロパティを満たすために、空のスポットはそのスポットの最小の子で繰り返し埋められます。

削除した後の最後の例を見てみましょうA(空の場所を でマークします*)。

[*][BC][DEFG][H-------]
[B][*C][DEFG][H-------]
[B][DC][*EFG][H-------]
[B][DC][HEFG]

これは、あなたが与えた出力にも対応しています。

于 2013-05-28T14:54:24.337 に答える