理由は二つの異なる概念のもの"ヒープ"?
-
18-09-2019 - |
質問
されている理由は何でしょうか実行時のヒープ使用のための動的メモリの割り当てC-スタイルの言語 のデータ構造 両方のヒープ"?いつ?
解決
ドナルド・クヌースは言う(コンピュータプログラミング、第三エドのアートを、第1巻、P 435。。。):
数人の著者は、使用可能なメモリのプールを呼び出すために約1975を開始した「ヒープ。」
彼は、任意の特定の論文への参照を与えるものではありませんが、プライオリティキューに関連した用語「ヒープ」の使用は、言葉の伝統的な意味であることを言うんどの作家と言っていません。
他のヒント
彼らは同じ名前を持っていますが、彼らは本当に(概念的にも)似ていません。メモリヒープを使用すると、「洋服の山」として洗濯バスケットを参照するのと同じ方法で、ヒープと呼ばれています。この名前は、メモリが割り当てられ、自由に割り当てを解除することができ、多少厄介な場所を示すために使用されます。 (あなたが指摘参照Wikipediaのリンクなど)のデータ構造はかなり異なっている。
名前の衝突が残念ですが、すべてが神秘的ではありません。 のヒープデータ構造のための単語ののなど、杭、コレクション、グループを意味するために使用される小型、一般的な単語である使用前の日付(私はかなり確信している)プールの名前メモリの。実際には、のプールのは、私の意見では、後者のためのより良い選択だったでしょう。 ヒープのデータ構造ではなく、メモリ・プールに嵌合(パイルのような)垂直構造を暗示します。私たちは、データ構造の背後にある基本的な考え方は、ヒープの最上部にある最大の要素(およびサブヒープ)を保っているのに対し、階層としてメモリ・プールのヒープを考えていません。
データ構造は半ば60年代にまでさかのぼりHeap(ヒープ)。メモリプール、初期70年代ヒープ。 (メモリプールを意味する)用語ヒープは Wijngaarden の議論でのことで、少なくとも、早ければ1971年のように使用されましたアルゴル。
おそらくデータ構造としてのヒープの最古の使用は7年前
で発見されました
ウィリアムズ、J. W. J. 1964 "アルゴリズム232 - ヒープソート"、ACMの通信 7(6):347から348
実際には、(バディブロックするを参照)、メモリが割り当てられている方法について読むことを思い出させますデータ構造におけるヒープのます。
ヒープのようなデータ構造は、利用可能なメモリの割り当てを求めるアルゴリズムによって使用されます。以下は、 http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.htmlから抜粋されます>。
new
が呼び出されると、、それはあなたの要求のためのサイズに合った空きメモリブロックを探し始めます。メモリのようなブロックが発見されると仮定すると、予約されたようにそれがマークされ、その場所へのポインタが返されます。妥協があなたのオブジェクトのサイズよりも大きい最小の空きブロックを見つけること、またはメモリが適合を必要と最初のものを返すため、メモリ全体をスキャンする間に行わなければならないため、これを達成するには、いくつかのアルゴリズムがあります。メモリのブロックを取得する速度を向上させるために、メモリの空きと予約領域は、ヒープと呼ばれるバイナリツリーと同様のデータ構造に維持されます。
口語的な用語は、メモリおよびヒープメモリはC ++標準で使用されていないスタック。標準は、静的ストレージ、スレッドストレージ、自動ストレージ、および動的ストレージを使用します。
続きを標準のストレージDuractionセクションのnoreferrer">
Q。ヒープとは何ですか?
A.ヒープは、オブジェクトのコレクションは、互いの上に置いてある。 あなたの質問への回答:
ご存知のようにメモリヒープとバイナリヒープの両方が同じ概念を使用しています。
バイナリヒープは、ヒープの形で順序付けられた方法でデータ格納の同じ概念に従うデータ構造であるのに対し、データがプログラムに記述されたのと同じ順序でメモリにヒープの形で格納されている(上のデータ他の)。
私はあなたがコメント欄で何を考えて知ってみましょう。
おそらく実装最初のメモリヒープは、ヒープ構造で管理されたのですか?