ヒープ: 実行時メモリまたはデータ構造?接続は何ですか?

固有の概念、共有名: ランタイム ヒープとデータ構造

コンピューター サイエンスの分野では、「ヒープ」という用語は以下を指します。ランタイム ヒープと特定のデータ構造という 2 つの異なる概念です。命名法におけるこの奇妙な重複が混乱を引き起こし、次のような疑問が生じました: これら 2 つのエンティティの間には根本的な関係はありますか?

ランタイム メモリ割り当てのヒープ用語の起源

ドナルド・クヌース氏の独創的な著作『The Art of Computer Programming』によると、「ヒープ」という用語は、 1970 年代半ばに、C などの言語で動的メモリ割り当てに使用されるメモリ プールを説明しました。このメモリ領域は直接アドレス指定できず、プログラムがメモリを要求したり解放したりすると拡大または縮小します。 「ヒープ」という名前は、オブジェクトが乱雑に積み上げられたものに似た、そのしばしば無秩序で秩序のない性質からインスピレーションを得たと考えられます。

ヒープ データ構造

対照的に、ヒープ データ構造は、効率的な優先キュー操作に使用される完全なバイナリ ツリーです。ヒープ内の要素は、ヒープ プロパティを維持する特定の方法で格納されます。つまり、各ノードはその子以上 (最小ヒープの場合)、または以下 (最大ヒープの場合) です。この構成により、優先順位に基づいて要素を高速に挿入および抽出できます。

共通の語源、異なる概念

ヒープの 2 つの概念は、機能と点で明らかに異なります。使用法には、語源に関連性がある可能性があります。 「ヒープ」という用語はもともと英語でオブジェクトの山を指し、ランタイム ヒープの組織化されていない性質と一致しています。この言葉は後に、特定の言語で土や岩の山を表すように進化し、ヒープ データ構造の階層構造にインスピレーションを与えた可能性があります。

結論

共通の名前にもかかわらず、ランタイム ヒープとヒープ データ構造は、コンピューター プログラミングにおいて異なる役割を持つ根本的に異なる概念です。前者は動的なメモリ割り当てを提供し、後者は効率的な優先キュー操作を容易にします。両方の概念の「ヒープ」という用語の由来はまだ推測の域を出ませんが、それぞれの特性との関連性は否定できません。

以上がヒープ: 実行時メモリまたはデータ構造?接続は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。