1

DSA のクラスを受講してから 10 年近くになります。ウィキペディアの並べ替えアルゴリズムのリストを調べましたが、これほど目立ったものはありません。これはプライオリティ キューの実装の一部であり、並べ替えの一部はプッシュ関数 ( EnQueue) で発生し、もう 1 つはポップ関数 ( DeQueue) で発生するようです。

これが元のMathematicaコードですが、ほとんどの人はMathematicaに慣れていないので、各関数の下を少し翻訳しました。

EnQueue[q : queue[ar_, n_, pred_], val_] := Module[{i, j},
  If[n == Length[ar], ar = Join[ar, makeArray@Length@ar]];
  n++; ar[[n]] = val;
  i = n;
  While[True,
   j = Quotient[i, 2];
   If[j < 1 || pred[ar[[j]], ar[[i]]],
    Break[]
    ];
   ar[[{i, j}]] = {ar[[j]], ar[[i]]};
   i = j;
   ];
  q
  ]

このEnQueue関数は、最初に要素数がnheap のサイズに達しているかどうかを確認し、達しているar場合はヒープを 2 倍にします。次に、要素の数を増やし、新しい要素をそのインデックスに格納します( Mathematicaのインデックスは0ベースではなく1ベースです)。次に、(新しい要素の) そのインデックスに設定し、にi設定するループに入ります。つまり、ヒープの中央にある要素です。ここで、 if (これは、私が知る限り、 if (中間の要素)が(新しい要素) の前にあることを確認することと同じです)、ブレークします。それ以外の場合は、とで要素を交換しますjfloor(i/2)j < 1i == 1ar[j]ar[i]ij、そして続けます。そのため、2 回目の反復では、中央をi指すことから始め、 4 分の 1 を指すようにします。j

DeQueue[queue[ar_, n_, pred_]] := 
 Module[{i, j, res = ar[[1]]},
  ar[[1]] = ar[[n]]; ar[[n]] = Null; n--;
  j = 1;
  While[j <= Quotient[n, 2],
   i = 2 j;
   If[i < n && pred[ar[[i + 1]], ar[[i]]],
    i++
    ];
   If[pred[ar[[i]], ar[[j]]],
    ar[[{i, j}]] = {ar[[j]], ar[[i]]};
    ];
   j = i];
  res]

一方、ヒープの前面を戻し、ヒープの背面DeQueueを前面に移動します (そして、背面の設定を解除し、要素の数を減らします)。次に、前を指すことから始まり、double に設定することから始まるループに入ります。範囲内(要素を指している) であるが、次の要素に関して順不同である場合、インクリメントされます。が (フロントに対して、つまり、フロントがに対して順不同である場合)の場合、2 つの位置が交換され、 があった位置に設定されます。真ん中を通過するまでループを続けます。jijiiijijij

上記の太字の部分がほとんどで、わかりません。でヒープの半分をソートし、 で新しい要素のソートの一部を行っていると思いますが、よくわかりません...DeQueueEnQueue

4

1 に答える 1

4

エンキューは私には最小ヒープルーチンのようです
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps

デキューは、配列の最初の項目に格納されているヒープの一番上の項目を削除し、それを配列の最後の項目に置き換え、ヒープの下に移動します。アイテムよりも小さい (兄弟がある場合は、その兄弟よりも小さい)。小さい子がなくなると、つまり、アイテムがヒープの底に達するか、その子 (または子、1 つしかない) よりも小さくなると、それは停止します。

編集:「エンキュー」と「デキュー」という言葉は、それがキューであることを示唆しています。アルゴリズムは配列に実装されたバイナリ ヒープであるため、これは優先キューです。

于 2015-03-20T14:28:55.340 に答える