-5

バイナリ ヒープについて調査しましたが、このプログラムをどうするかについてまだ非常に混乱しています。何らかのガイダンスを得ることができれば、本当に感謝しています。

k-ary ヒープはバイナリ ヒープ (k = 2) に似ていますが、(1 つの例外を除いて) 非リーフ ノードには 2 つの子ではなく k 個の子があります。次の操作をサポートするために、任意の k ≥ 2 の最小優先度キューとして k-ary ヒープを実装します。

• insert (x): 要素 x をヒープに挿入します。

• extract-min(): 最小のキーを持つヒープの要素を削除して返します。

k-ary ヒープは、事前定義されたサイズの配列を使用して実装されます。また、k = 2、4、6、8、10 の入力ファイルが与えられた場合に一連の操作を実行するのに必要な時間を測定することにより、さまざまな k の値に対するデータ構造の相対的な効率を調べます。入力ファイルでは、「IN」は略「EX」はインサートの略で、「EX」は抽出分操作の略です。

4

1 に答える 1

3

バイナリ ヒープは、ほぼ完全な (= 完全な)バイナリ ツリーとして実装されます。k-ary ヒープの場合、おそらくalmost full k-ary tree[ツリー内のすべてのレベルがいっぱいです。ただし、ツリーを左から右に埋める最後のレベルは除きます] を生成し、元のヒープと同じ操作を繰り返しますが、ノードごとに 2 つ以上の子。

heap ops、特に、および上記のヒントに関する知識がheapifyあれば、k-ary ヒープを実装するのは難しくありません。

これを配列として実装するには、二分木を配列として実装する方法に従ってください。また、完全な k 分木を配列として実装する場合は、これらの考え方に従ってください。

于 2011-09-26T15:36:11.993 に答える