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

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

1. 優先キューの応用例

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

2. 優先キューの実装原理

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

1 .任意のノードの値は、その子ノードの値以下です。

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

配列

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

3. JDK での優先キューの実装方法

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

変数

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

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

Eclipse

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

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

 public PriorityQueue(int initialCapacity,
             Comparator<? super E> 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;
  }

まず、offer メソッドはパラメーターが空であるかどうかを判断し、変数 modCount をインクリメントします。次に、配列が範囲外になるかどうかを判断し、現在の要素が 0 の場合は要素を追加します。それ以外の場合は、siftUp 操作を実行します。

 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;
  }

優先キューのプロパティ 1 を確保するには、各要素を挿入するときに、ノードの親と比較して正しい位置を見つける必要があります。一部のデータ構造の本では、この操作はパーコレート アップと呼ばれています。

エンキュー操作が完了しました。次のステップはデキュー操作、つまり、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.

無料のJavaビデオチュートリアル

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

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