Cormenのヒープソート構造

Question

私はCormenのアルゴリズム帳のヒープソートの章を通じてつもりですが、文の下に理解して捕まってしまった

：

ほとんどのコンピュータで

、LEFT手順を 命令で2iを計算するには、 の左辺の2進表現を1ビットの位置にシフトするだけです。

同様に、RIGHTプロシージャは、 を1ビット位置だけ左にシフトし、次に を下位ビットとして1に加算することによって、2i + 1を迅速に計算できます。 PARENTプロシージャは、右1ビット位置をシフトすることによって [i/2]を計算できます。 heapsortの良い実装は、多くの場合、これらのプロシージャを「マクロ」または「インライン」の プロシージャとして実装します。

ここではLEFTプロシージャとはどのように計算されますか。

同様に、右手順の計算方法は&です。

マクロまたはインラインプロシージャを使用してプロシージャを実装することを意味します。

非常に多くの人から、これはアルゴリズムを学ぶのに最適な本だと知りましたが、著者がここで説明しようとしていることを理解できません。

Answer 1

parent、left、およびright手順は簡単です現在の要素（iに）が与えられた場合、parent,left、およびrightの要素を得るための計算。

親はi/2

の床で左は2i

で右ご提供例を考えてみましょう2i + 1

---

です。 一般的に配列は0ベースですが、あなたの例は1ベースのようです。

私たちは配列を持っています。それはAと呼ばれ、A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]です。

のは、我々は、上記の計算を使用して10 あるA[3]を見ているとしましょう、A[3]の親ですA[1]ある16 A[3] の左の子は9 A[3]の右の子があるA[6]ですほとんどのコンピュータ3.

---

あるA[7]、LEFT手順は単に私のバイナリ表現をシフトすることによって一つの命令で2Iを計算することができるが1ビット位置だけ左。

同様に、RIGHTプロシージャは、1ビット位置だけ左にあるiのバイナリ表現をシフトし、次に下位ビットとして1を加算することによって、2i + 1を迅速に計算できます。 PARENTプロシージャは、iを1ビット右にシフトすることによって[i/2]を計算できます。ヒープソースの実装は、マクロプロシージャまたはインラインプロシージャとしてこれらのプロシージャを実装することがよくあります。

これは、プロセッサレベルでのこれらの機能の複雑さを示しています。要点は、parent,left、およびrightは通常プロセッサ上の1つまたは2つの命令で実行できることです。

inline proceduresのコメントは、コンパイラの最適化について説明しています。コンパイラは、通常、アセンブリコードを自分で記述すると、人間よりも多くのアセンブリ命令を生成します。したがって、このコメントは、（parent、left、およびright）プロシージャを、適切なコンパイラ最適化が利用可能であると仮定して、単一（または2つ）の命令にコンパイルすることができるということだけです。

これらの手順が実際にプロセッサレベルでどのように実行されているかを理解しようとしている場合は、bit shiftingを読む（または他の回答を読む）ことができます。

Answer 2

ノード＃2のバイナリ表現を見ると、0000 0010（読みやすくするために4ビットで分割）です。左シフトとは、すべてのビットが左のビットに置き換わることを意味し、右のネイバーを持たないビットはすべて0になります。

したがって、0000 0001には0000 0010が、 2は0000 0100になります。最も右のビットがゼロになったことが分かりましたか？また、バイナリ表現0000 0100は4であり、ノード＃2の左の子が有する正確な同じ番号である。

あなたがそれを理解すれば、残りは簡単です。 +1を伴う左シフトは、0000 0010（2）を0000 0101（5）に変更する。これは右の子のノード番号です。

表現から何かを切り捨てるので、ややトリッキーなのは親です。ノード＃3 0000 0011の親を取得したい場合は、右に1回移動して0000 0001になります。これは両方の子に適用され、最も右のビットが切り捨てられます。

今すぐマクロ&インライン。インラインは、ある種のプログラミング言語（例えば、C++で学んだことなど）のメソッドであり、与えられたタスクをスピードアップできるかどうか評価する必要があるコンパイラに指示します。これは、（あなたの左の&右シフトタスクのように）頻繁に発生する非常に単純なタスクには、ほとんど役に立ちます。このような基本的なアルゴリズムは非常に効率的でなければならないので、これは理にかなっています。なぜなら、より多くのノードを処理しなければならないほど、処理速度が遅くなるからです。 マクロはほぼ同じです。何度も実行されるタスクを保存するだけです。あなたがよりよく理解するためにGoogleができ

いくつかのフレーズ： 左シフトビット演算 インライン方法C++

最高の願い、

ESSI