ホームページ >Java >＆＃＆チュートリアル >Java データ構造の最小ヒープと最大ヒープの原理と実装の詳細な説明

Java データ構造の最小ヒープと最大ヒープの原理と実装の詳細な説明

WBOY転載: 2022-09-05 17:30:292450ブラウズ

この記事では、java に関する関連知識を提供します。コンピューターサイエンスでは、ヒープの実装は、配列で使用できるツリーに基づく特別なデータ構造です。ツリー構造を構築し、次の条件を満たした後、ヒープのプロパティについては、Java データ構造におけるヒープについて説明しましょう。興味のある方は、さらに詳しく学ぶことができます。

## 推奨学習: 「

java ビデオチュートリアル」

1. はじめに

ヒープの歴史

ヒープのデータ構造には、2 ～ 3 ヒープ、B ヒープ、フィボナッチヒープなどのさまざまな形式があり、Java API で最も一般的に使用されるのは、JWJ Williams によって紹介された優先キューの実装に使用されるバイナリヒープです。 1964 年にヒープソートアルゴリズムのデータ構造として開発されました。さらに、ヒープは、ダイクストラのアルゴリズムなど、いくつかの効率的なグラフアルゴリズムでも非常に重要です。

2. ヒープデータ構造

コンピュータサイエンスでは、ヒープの実装はツリーに基づく特別なデータ構造であり、array.body 上にツリー構造を構築し、プロパティを満たすことができます。ヒープの;

最小ヒープ: P が C の親ノードの場合、P のキー (または値) は C の対応する値以下である必要があります。

最大ヒープ: 最小ヒープの定義の逆で、最大ヒープ (最大ヒープ) では、P のキー (または値) は、 C の対応する値。

3. ヒープコードの実装

1. 実装の概要

Java API でのヒープの実装は、主に遅延キューバイナリヒープを実装するために、Brother Fu はコードのこの部分を分離して、小さなヒープと大きなヒープの実装について学びます。

ヒープのデータ構造の概要から、小さなヒープと大きなヒープの唯一の違いは要素の並べ替え方法であることがわかります。つまり、要素を格納および取得するときと、要素を埋めたり削除するときは、ソート方法が異なります。

2. ヒープへの実装

要素をヒープに格納する場合、その特性に従うために、格納プロセス中にキューの最後にある要素が比較され、上方に移動されます。。

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx，相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素，大于父节点元素，则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素，则进行替换
        logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(e), k);
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    logger.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}

add メソッドをヒープに追加する実装では、最終的に siftUpComparable メソッドを呼び出して、並べ替え方法で処理します。この並べ替えの CompareTo メソッドは、特定の MinHeap および MaxHeap によって実装されます。

図に示すように、ヒープ要素 2 を例に挙げます。

まず要素 2 をキューの最後にハングし、(k - 1) >>> 1 を通じて親ノードの位置を計算し、比較します。対応する要素と判定を交換します。

交換プロセスには 2->6、2->5 が含まれており、交換が完了すると要素が保存されます。

3. ヒープから

要素を削除するのは実際には非常に簡単で、ルート要素を削除して直接ポップアウトするだけです。ただし、ルート要素を移行した後、反対側に移行するための別の最小要素を見つける必要があるため、残りの手順は複雑です。このプロセスは、ヒープに入るのとはまったく逆で、継続的な下方への移行のプロセスです。

private void siftDownComparable(int k, E x) {
    // 先找出中间件节点
    int half = size >>> 1;
    while (k < half) {
        // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        // 左子节点与右子节点比较，取最小的节点
        if (right < size && compareTo((E) c, (E) queue[right]) > 0) {
            logger.info("【出队】左右子节点比对，获取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
            c = queue[child = right];
        }
        // 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。
        if (compareTo(x, (E) c) <= 0) {
            break;
        }
        // 目标值小于c值，位置替换，继续比较
        logger.info("【出队】替换过程，节点的值比对。上节点：{} 下节点：{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
        queue[k] = c;
        k = child;
    }
    // 把目标值放到对应位置
    logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
    queue[k] = x;
}

要素を下方向に継続的に移行します。このプロセスでは、左右の子ノードの値を比較し、最小のものを見つけます。したがって、プロセス全体は山に入るよりも面倒になります。

ここでは、ポップアップ要素 1 を例として取り上げ、ヒープの末尾にある要素を対応する位置に置き換えます。全体のプロセスは 6 つの写真に分かれています。

図 3 から図 4 へ、ルート要素を下に移動し、子要素と比較し、位置を置き換えます。この位置を 8 と比較して 8 未満の場合は、下方向に移動し続けます。
図 4 から図 5 へ、移行を続行します。元のノード 4 に対応する 2 つのサブ要素は両方とも 8 より大きくなります。この時点で停止できます。
図 5 から図 6 へ、要素の位置を変更し、キューの末尾の要素を要素 1 の下方移行検出に対応する位置に置き換えます。

4. 小規模ヒープの実装

小規模ヒープは正のシーケンス比較です

public class MinHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return firstElement.compareTo(secondElement);
    }

}

テスト

@Test
public void test_min_heap() {
    MinHeap heap = new MinHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}

結果

17:21:30.053 [メイン] INFO queue.PriorityQueue - [エンキュー] 要素: 3 現在のキュー: [1,null,null,null,null,null,null,null,null,null, null ]
17:21:30.055 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 1 親: 0
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] 値の比較、親ノード: 1 ターゲットノード: 3
17:21:30.056 [main] INFO キュー。 PriorityQueue - [キューに入る] 完全な IDx: 1 Val: 3
現在のキュー: [1,3,null,null,null,null,null,null,null,null,null]

17 :21:30.056 [メイン] INFO queue.PriorityQueue - [エンキュー] 要素: 5 現在のキュー: [1,3,null,null,null,null,null,null,null,null,null]
17 :21 :30.056 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 2 親: 0
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 1 ターゲットノード: 5
17:21:30.056 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完全な IDx: 2 Val: 5
現在のキュー: [1,3,5,null,null,null,null,null,null,null,null]

17 :21:30.056 [メイン] 情報キュー.PriorityQueue - [エンキュー] 要素: 11 現在のキュー: [1,3,5,null,null,null,null,null,null,null,null]
17 :21 :30.056 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 3 親: 1
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 3 ターゲットノード: 11
17:21:30.056 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完全な IDx: 3 Val: 11
現在のキュー: [1,3,5,11,null,null,null,null,null,null,null]

17 :21:30.056 [メイン] INFO queue.PriorityQueue - [エンキュー] 要素: 4 現在のキュー: [1,3,5,11,null,null,null,null,null,null,null]
17 :21 :30.056 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 4 親: 1
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 3 ターゲットノード: 4
17:21:30.056 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 4 Val: 4
現在のキュー: [1,3,5,11,4,null,null,null,null,null,null]

17 :21:30.056 [メイン] INFO queue.PriorityQueue - [エンキュー] 要素: 6 現在のキュー: [1,3,5,11,4,null,null,null,null,null,null]
17 :21 :30.056 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 5 親: 2
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 5 ターゲットノード: 6
17:21:30.056 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 5 Val: 6
現在のキュー: [1,3,5,11,4,6,null,null,null,null,null]

17 :21:30.056 [メイン] INFO queue.PriorityQueue - [エンキュー] 要素: 7 現在のキュー: [1,3,5,11,4,6,null,null,null,null,null]
17 :21 :30.056 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 6 親: 2
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 5 ターゲットノード: 7
17:21:30.056 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 6 Val: 7
現在のキュー: [1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [ main ] INFO queue.PriorityQueue - [Enqueue] 要素: 12 現在のキュー: [1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main ] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 7 親: 3
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 11 ターゲットノード: 12
17:21:30.056 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 7 Val: 12
現在のキュー: [1,3,5,11,4,6,7,12,null,null,null]

17 :21:30.056 [メイン] INFO queue.PriorityQueue - [キューに入る] 要素: 15 現在のキュー: [1,3,5,11,4,6,7,12,null,null,null]
17 : 21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を見つけます。 k: 8 親: 3
17:21:30.056 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 11 ターゲットノード: 15
17:21:30.057 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 8 Val: 15
現在のキュー: [1,3,5,11,4,6,7,12,15,null,null]

17 :21:30.057 [メイン] INFO queue.PriorityQueue - [キューに入る] 要素: 10 現在のキュー: [1,3,5,11,4,6,7,12,15,null,null]
17 : 21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を見つけます。 k: 9 親: 4
17:21:30.057 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 4 ターゲットノード: 10
17:21:30.057 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 9 Val: 10
現在のキュー: [1,3,5,11,4,6,7,12,15,10,null]

17 :21:30.057 [メイン] INFO queue.PriorityQueue - [キューに入る] 要素: 9 現在のキュー: [1,3,5,11,4,6,7,12,15,10,null]
17 : 21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を見つけます。 k：10 親：4
17:21:30.057 [メイン] INFO queue.PriorityQueue - [キューに入る] 値の比較、親ノード: 4 ターゲットノード: 9
17:21:30.057 [メイン] INFO queue.PriorityQueue - [キューに入る] が完了しました Idx : 10 Val: 9
現在のキュー: [1,3,5,11,4,6,7,12,15,10,9]

17:21:30.057 [メイン] INFO キュー.PriorityQueue - [エンキュー] 要素: 8 現在のキュー: [1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null ,null ,null,null,null,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 11 親: 5
17:21:30.057 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 6 ターゲットノード: 8
17:21:30.057 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 11 Val: 8
現在のキュー: [1,3,5,11,4,6,7,12,15,10,9,8,null,null, null ,null,null,null,null,null,null,null,null,null]

17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値比率が正しい。上位ノード：1 下位ノード：3 位置置換
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 11 右: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 3 下位ノード: 4 位置置換
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 10 右: 9
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 結果を置き換え、最後に位置を変更します。 Idx: 4 Val: 8
17:21:30.057 [main] INFO heap.__test__.HeapTest - テスト結果: 1
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード: 3 下位ノード: 4 位置置換
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 11 右: 8
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 4 下位ノード: 8 位置置換
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 4 Val: 9
17:21:30.057 [main] INFO heap.__test__.HeapTest - テスト結果: 3
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Left and Right Children ノードを比較して最小値を取得します。左: 8 右: 5
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード：4 下位ノード：5 位置置換
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue]置換処理、ノード値比較。上位ノード: 5 下位ノード: 6 位置置換
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 5 Val: 10
17:21:30.057 [main] INFO heap.__test__.HeapTest - テスト結果: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Left and Right Children ノードを比較して最小値を取得します。左: 8 右: 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード：5 下位ノード：6 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 10 右: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 6 下位ノード: 7 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 6 Val: 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - テスト結果: 5
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Left and Right Children ノードを比較して最小値を取得します。左: 8 右: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード:6 下位ノード:7 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue]置換処理、ノード値比較。上位ノード: 7 下位ノード: 10 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 結果を置換し、最後に位置を変更します。 Idx: 5 Val: 12
17:21:30.058 [main] INFO heap.__test__.HeapTest - テスト結果: 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード：7 下位ノード：8 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 11 右: 9
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 8 下位ノード: 9 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 4 Val: 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - テスト結果: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード：8 下位ノード：9 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue]置換処理、ノード値比較。上位ノード: 9 下位ノード: 11 位置置換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：15

Process finished with exit code 0
小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆实现

小堆是一个反序比对

public class MaxHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return secondElement.compareTo(firstElement);
    }

}

测试

@Test
public void test_max_heap() {
    MaxHeap heap = new MaxHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}

结果

17:23:45.079 [メイン] INFO queue.PriorityQueue - [エンキュー] 要素: 3 現在のキュー: [1,null,null,null,null,null,null,null,null,null, null ]
17:23:45.081 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 1 親: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノード値: 1 格納場所: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [キューに入る] 完了 Idx: 0 Val: 3
現在のキュー: [3,1,null, null,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 要素: 5 現在のキュー: [3,1, null ,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 2parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノード値: 3 格納場所: 2
17:23:45.081 [main] INFO queue.PriorityQueue - [キューに入る] Complete Idx: 0 Val: 5
現在のキュー: [5,1,3, null,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 要素: 11 現在のキュー: [5,1, 3 ,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 3parent: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 1 格納場所: 3
17:23:45.081 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 1 親: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノード値: 5 格納場所: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [キューに入る] Complete Idx: 0 Val: 11
現在のキュー: [11,5,3, 1,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 要素: 4 現在のキュー: [11,5, 3 ,1,null,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 4 親: 1
17:23:45.082 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 5 ターゲットノード: 4
17:23:45.082 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 4 Val: 4
現在のキュー: [11,5,3,1,4,null,null,null,null,null,null]

17 :23:45.082 [メイン] 情報キュー.PriorityQueue - [エンキュー] 要素: 6 現在のキュー: [11,5,3,1,4,null,null,null,null,null,null]
17 :23 :45.082 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 5parent: 2
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 3 格納場所: 5
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を検索します。 k: 2 親: 0
17:23:45.082 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 11 ターゲットノード: 6
17:23:45.082 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完全な IDx: 2 Val: 6
現在のキュー: [11,5,6,1,4,3,null,null,null,null,null]

17 :23:45.082 [メイン] 情報キュー.PriorityQueue - [エンキュー] 要素: 7 現在のキュー: [11,5,6,1,4,3,null,null,null,null,null]
17 :23 :45.082 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 6parent: 2
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 6 格納場所: 6
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 2 親: 0
17:23:45.082 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 11 ターゲットノード: 7
17:23:45.082 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 2 Val: 7
現在のキュー: [11,5,7,1,4,3,6,null,null,null,null]

17 :23:45.082 [メイン] 情報キュー.PriorityQueue - [エンキュー] 要素: 12 現在のキュー: [11,5,7,1,4,3,6,null,null,null,null]
17 :23 :45.082 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を検索します。 k: 7parent: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 1 格納場所: 7
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 3parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 5 格納場所: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k：1 親：0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置が置換され、サイクルが継続します。親ノード値: 11 格納場所: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] Complete Idx: 0 Val: 12
現在のキュー: [12,11,7, 5,4,3,6,1,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 要素: 15 現在のキュー: [12,11, 7 ,5,4,3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 8parent: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 置換処理、親ノードと子ノードの位置が入れ替わり、サイクルが継続します。親ノードの値: 5 格納場所: 8
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 3parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 11 格納場所: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 1 親: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノード値: 12 格納場所: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] Complete Idx: 0 Val: 15
現在のキュー: [15,12,7, 11,4,3,6,1,5,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 要素: 10 現在のキュー: [15,12, 7 ,11,4,3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 9parent: 4
17:23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 4 格納場所: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 4 親: 1
17:23:45.083 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 12 ターゲットノード: 10
17:23:45.083 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 4 Val: 10
現在のキュー: [15,12,7,11,10,3,6,1,5,4,null]

17 :23:45.083 [メイン] INFO queue.PriorityQueue - [キューに入る] 要素: 9 現在のキュー: [15,12,7,11,10,3,6,1,5,4,null]
17 : 23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] 現在のノードの親ノードの位置を見つけます。 k: 10 親: 4
17:23:45.083 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 10 ターゲットノード: 9
17:23:45.083 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 10 Val: 9
現在のキュー: [15,12,7,11,10,3,6,1,5,4,9]

17 :23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] 要素: 8 現在のキュー: [15,12,7,11,10,3,6,1,5,4,9,null,null, null, null,null,null,null,null,null,null,null,null,null]
17:23:45.083 [main] INFO queue.PriorityQueue - [キューに入る] の親ノードの位置を見つけます現在のノード。 k: 11parent: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [キューに入る] 置換処理、親ノードと子ノードの位置が入れ替わり、サイクルが継続します。親ノードの値: 3 格納場所: 11
17:23:45.083 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 5parent: 2
17:23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] 置換プロセス、親ノードと子ノードの位置を置換し、サイクルを継続します。親ノードの値: 7 格納場所: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [キューに入る] 現在のノードの親ノードの位置を見つけます。 k: 2 親: 0
17:23:45.083 [メイン] INFO キュー.PriorityQueue - [キュー] 値の比較、親ノード: 15 ターゲットノード: 8
17:23:45.083 [メイン] INFO キュー。 PriorityQueue - [キューに入る] 完了 Idx: 2 Val: 8
現在のキュー: [15,12,8,11,10,7,6,1,5,4,9,3,null,null, null ,null,null,null,null,null,null,null,null,null]

17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値比率が正しい。上位ノード：15 下位ノード：12 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値比較。上位ノード: 12 下位ノード: 11 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 1 右: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 11 下位ノード: 5 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 結果を置換し、最後に位置を変更します。 Idx: 8 Val: 3
17:23:45.083 [main] INFO heap.__test__.HeapTest - テスト結果: 15
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード: 12 下位ノード: 11 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左：5 右：10
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 11 下位ノード: 10 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 結果を置換し、最後に位置を変更します。 Idx: 4 Val: 9
17:23:45.083 [main] INFO heap.__test__.HeapTest - テスト結果: 12
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード: 11 下位ノード: 10 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 左右の子ノードを比較して最小値を取得します。左: 5 右: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 10 下位ノード: 9 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 結果を置換し、最後に位置を変更します。 Idx: 4 Val: 4
17:23:45.083 [main] INFO heap.__test__.HeapTest - テスト結果: 11
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード：10 下位ノード：9 位置置換
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue]置換処理、ノード値比較。上位ノード: 9 下位ノード: 5 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 3 Val: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 10
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Left and Right Children ノードを比較して最小値を取得します。左: 5 右: 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード：9 下位ノード：8 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue]置換処理、ノード値比較。上位ノード: 8 下位ノード: 7 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 5 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 9
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Left and Right Children ノードを比較して最小値を取得します。左: 5 右: 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 8 下位ノード: 7 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 2 Val: 6
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Left and Right Children ノードを比較して最小値を取得します。左: 5 右: 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換処理、ノード値の比較。上位ノード: 7 下位ノード: 6 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 2 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード: 6 下位ノード: 5 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 1 Val: 4
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード: 5 下位ノード: 4 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 1 Val: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 5
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換プロセス、ノード値の比較。上位ノード: 4 下位ノード: 3 位置置換
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、最終置換位置。 Idx: 1 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 4
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 置換結果、結局は立場を変える。 IDx: 0 値: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - テスト結果: 1

終了コード 0

処理は終了しました。大山は逆出力結果で、大きい順から小さい順にソートして出力されます。

スペースの大きな山: [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null, null、null、null、null、null]

推奨学習:「Java ビデオチュートリアル」

以上がJava データ構造の最小ヒープと最大ヒープの原理と実装の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明：

この記事はjb51.netで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。

前の記事：Java Web 動的 Web サイト開発チュートリアル次の記事：Java Web 動的 Web サイト開発チュートリアル

続きを見る