JDKでのプライオリティキューの実装方法の詳細な説明

この記事では主にJDKソースコードのPriorityQueueを詳しく紹介しますので、興味のある方は参考にしてください

1. 優先キューの応用例

例えば、オペレーティング システムでのプロセス スケジューリングの実現可能なアルゴリズムは、優先キューを使用することです。新しいプロセスが fork() されると、そのプロセスはまずキューの最後に配置され、オペレーティング システム内のスケジューラが継続的に処理を実行します。このプロセスからの切り替えでは、優先度の高いプロセスが優先キューから取り出されて実行されます。クローラ システムの実行時には、優先度の高いタスクをループ内の優先キューから取り出してクロールする必要があることがよくあります。このようなタスクが優先度によって分割されていない場合、たとえば、オペレーティング システムの優先度の低いプロセスがリソースを占有し続け、優先度の高いプロセスが常にキュー内で待機しているなど、システムが失敗する可能性が考えられます。さらに、プライオリティ キューには、貪欲なアルゴリズムにもいくつかのアプリケーションがあります。

優先キューの実装は、次の 2 つのプロパティ (ヒープ プロパティ) を満たす必要があるバイナリ ヒープの構造を使用します。 ここでは、スモール トップ ヒープを例に挙げます。 :

2. すべてのノードが上から下、左から右に埋められ、完全な二分木になります。
これらの2つのルールに基づいて、バイナリヒープは実装で

を使用することがよくあります。JDKでのバイナリヒープ(優先キュー)の実装を検討してみましょう。

ソース コードを研究する最良の方法は、各ステップでの

の変更を確認することです。デモを作成してソースにデバッグするだけです。確認するコード:

ここでは、優先キューを作成し、それに 3 つの要素を追加します。

Editorを使用している場合は、次のキーを押します。 F5 キーを押してソース コードを入力します。 中央:

コードはここで実行されます。最初のパラメーターは配列のデフォルトのサイズであり、2 番目のパラメーターは要素を比較するための Comparator です。ここでのデモは比較的単純です。優先キューを使用する場合は、独自のコンパレーターを実装することを選択できます。

public PriorityQueue(int initialCapacity, Comparator comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }

次に、要素を追加するときのオファー操作を見てみましょう:

public boolean offer(E e) { if (e == null) throw new NullPointerException(); //记录了队列被修改的次数 modCount++; int i = size; if (i >= queue.length) //扩容 grow(i + 1); //增加元素个数 size = i + 1; if (i == 0) //第一次添加元素，直接放到第0个位置即可 queue[0] = e; else //需要将元素放到最后，再做上滤操作 siftUp(i, e); return true; }

private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //元素拷贝 queue = Arrays.copyOf(queue, newCapacity);

上記のコードはキューを拡張します。ソース コード内の

も非常に明確です。まず、現在の配列サイズが十分に小さいかどうかを判断し (<64)、サイズを拡張します。それ以外の場合は、元のサイズを 50% 大きくします。なお、最終的にはサイズがオーバーフローするかどうかがここで判断される。

private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

拡張する必要があるサイズがすでに 0 未満の場合は、明らかにオーバーフローしており、ここで OutOfMemory 例外がスローされます。

private void siftUpUsingComparator(int k, E x) { while (k > 0) { //计算父亲节点的下标 int parent = (k - 1) >>> 1; Object e = queue[parent]; //与父节点进行比较 if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }

エンキュー操作が完了しました。次のステップはデキュー操作、つまり、poll() 操作です:

public E poll() { if (size == 0) return null; int s = --size; //自增变量，代表队列修改次数 modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); return result; }

このメソッドは、まず配列の最初の要素を結果として取得します (配列が小さい場合は、トップ ヒープ、ヒープの先頭は常に最小の要素です)、キューの最後の要素を最初の位置に置き、最後に siftDown を使用していくつかの調整を行い、キューのプロパティを確保します。この操作はパーコレート ダウンと呼ばれます。 。

private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; //这里k必须有孩子，故叶节点需要比较 while (k < half) { //以下几行代码到较小的那个儿子,用变量c表示 int child = (k << 1) + 1; //这里假设左儿子比较小 Object c = queue[child]; int right = child + 1; //左右儿子比较，如果右儿子小则将c赋值为右儿子 if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; //如果x比小儿子还小，说明k就是正确位置 if (comparator.compare(x, (E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = x; }

上図に示すように、下方フィルタリング処理中、k は常にその子と比較され、優先キューの順序が満たされると、ループは終了します。

【関連するおすすめ】

1.

2.FastJsonチュートリアルマニュアル

以上がJDKでのプライオリティキューの実装方法の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。