C スタイル言語でランタイム ヒープが動的メモリ割り当てに使用され、データ構造が両方とも「ヒープ」と呼ばれるのはなぜですか? 何か関係あるの？
32476 次
9 に答える
100
Donald Knuth は次のように述べています (The Art of Computer Programming、第 3 版、Vol. 1、p. 435)。
1975 年頃、何人かの著者が利用可能なメモリのプールを「ヒープ」と呼び始めました。
彼はどの著者が誰であるかは明らかにせず、特定の論文への言及もしていませんが、優先キューに関連して「ヒープ」という用語を使用することは伝統的な意味であると述べています。
于 2009-11-09T04:47:09.770 に答える
74
名前は同じですが、実際には (概念的にも) 似ていません。メモリ ヒープは、洗濯かごを「衣類の山」と呼ぶのと同じように、ヒープと呼ばれます。この名前は、メモリを自由に割り当てたり割り当て解除したりできるやや厄介な場所を示すために使用されます。データ構造 (参照するウィキペディアのリンクが指摘しているように) はまったく異なります。
于 2009-11-09T04:17:23.987 に答える
39
名前の衝突は残念ですが、それほど神秘的ではありません。ヒープは、パイル、コレクション、グループなどを意味するために使用される小さな一般的な単語です。データ構造に対するこの単語の使用は、メモリのプールの名前よりも前のものです (私はかなり確信しています)。実際、私の意見では、後者にはプールの方がはるかに適していたでしょう。ヒープは、データ構造には適合しますが、メモリプールには適合しない垂直構造 (パイルのような) を暗示します。データ構造の背後にある基本的な考え方は、ヒープ (およびサブヒープ) の一番上に最大の要素を保持することですが、メモリ プール ヒープを階層的なものとは考えていません。
ヒープのデータ構造は 60 年代半ばにさかのぼります。70年代初頭のメモリプールをヒープします。ヒープ (メモリ プールを意味する) という用語は、少なくとも 1971 年にはWijngaardenによってAlgol の議論で使用されていました。
おそらくデータ構造としてのヒープ
の最も初期の使用は、7 年前に
Williams、JWJ 1964.「アルゴリズム 232 - ヒープソート」、ACM の通信7(6): 347-348
于 2009-11-09T05:24:59.793 に答える
6
実際、メモリの割り当て方法 ( Buddy Blocksを参照) を読むと、データ構造のヒープを思い出します。
于 2009-11-09T04:20:51.337 に答える
6
ヒープのようなデータ構造は、使用可能なメモリ割り当てを見つけるアルゴリズムによって使用されます。以下はhttp://www.cprogramming.com/tutorial/virtual_memory_and_heaps.htmlからの抜粋です。
が
new呼び出されると、要求のサイズに適合する空きメモリ ブロックの検索が開始されます。そのようなメモリ ブロックが見つかった場合、それは予約済みとしてマークされ、その場所へのポインタが返されます。オブジェクトのサイズよりも大きい最小の空きブロックを見つけるためにメモリ全体をスキャンするか、必要なメモリが収まる最初のブロックを返すかの間で妥協する必要があるため、これを達成するためのアルゴリズムがいくつかあります。メモリのブロックを取得する速度を向上させるために、メモリの空き領域と予約領域は、ヒープと呼ばれるバイナリ ツリーに似たデータ構造で維持されます。
于 2014-11-02T19:10:00.573 に答える
-5
おそらく最初に実装されたメモリ ヒープは、ヒープ構造によって管理されたのでしょうか?
于 2009-11-09T04:15:45.840 に答える