この記事では、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)); }
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; }
小規模ヒープは正のシーケンス比較です
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]
小堆是一个反序比对
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 サイトの他の関連記事を参照してください。