ヒープとスタック:それらを際立たせるものは何ですか?

プログラマーとして、「ヒープ」と「スタック」という用語に出くわす可能性があります。初心者にとって、これら2つの用語を同じ意味で誤って使用することは広く行われています。

データ構造コースの学生と経験豊富なプログラマーは、これら2つのデータ構造を簡単に区別できますが、他の人には同じように見える場合があります。

プログラマーは、この2つを区別し、実際のプログラミング状況で適切に使用する必要があります。インタビュアーは、申請者にシナリオを提供し、次に最も適切なデータ構造を求めることに熱心であることがよくあります。

ヒープ、スタック、それらの違い、および関連するアプリケーションについて詳しく見ていきます。

ヒープとは何ですか?

プログラマーにとってのヒープは、通常、「優先度付きキュー」と呼ばれることが多い特別なツリーデータ構造です。完全にバランスの取れたバイナリツリー構造であり(完全なバイナリツリーのすべてのレベルが最後のレベルを除いて満たされていることを思い出してください)、ヒーププロパティに従うヒープはバイナリヒープと呼ばれます。

ヒーププロパティは、ルートに最大値または最小値を配置する方法でツリーを構成します。

関連:無料でコーディングする方法を学ぶための最良の方法

最大ヒープでは、親ノードの値が子ノードよりも大きく、ツリーのルートに最大値が含まれます。または、最小ヒープはルートとして最小値を持つように構成され、各子ノードはその親よりも大きな値を持ちます。ヒーププロパティは、バイナリツリー内のすべてのノードに対して再帰的に真である必要があります。

ヒープは通常、線形配列を介して実装され、配列の最初の要素( Arr [0] )がルートを表します。特定のノードiについて、 Arr [(2 * i)+1]およびArr [(2 * i)+ 2]で子ノードを取得できます。同様に、親ノードはArr [(i-1)にあります。 / 2]インデックス。 JavaやC ++などのほとんどの言語には、すぐに使用できる最小ヒープと最大ヒープをユーザーに提供するライブラリが含まれています。

スタックとは何ですか?

スタックは、学生に教えられる最初のデータ構造の1つであり、見落としてはなりません。スタックは、実際のスタック(カード、プレートなど)と同じように動作するデータ構造です。スタックは一方の端でのみ操作を許可するため、LIFO(後入れ先出し)特性があります。対照的に、キューにはFIFO(First-In-First-Out)特性があり、両端での操作が可能です。

一般的なスタック操作は、プッシュ(スタックの最上位にデータを挿入)とポップ(最上位のデータ要素を削除)で構成されます。要件に応じて、ポインター、配列、またはリンクリストを介してスタックを実装できます。 C ++、C#、およびJavaにはすべて、すでにスタックが実装されているライブラリが含まれているため、必要なときにいつでも使用できます。

ヒープとスタック

ここまで読んだら、スタックとヒープの違いについてかなり良い考えがあります。スタックは線形でLIFO特性を持っていますが、ヒープはツリー構造であり、ヒーププロパティに従います。どちらにも異なるアプリケーションがあり、次のセクションで説明します。

漸近的な時間計算量分析の観点から、O(n)でバイナリヒープを構築し、O(1)で最小値または最大値を抽出できます。挿入と削除はO(log N)時間で実行できます。対照的に、挿入と削除はスタックでO(1)時間を要します。

代表的なアプリケーション

上記の理由により、ヒープは優先キューとして使用すると非常に効率的です。 PrimのMinimumSpanningTreeやDijkstraのShortestPathなどのグラフアルゴリズムは、通常、優先キューとしてヒープを利用します。ヒープのもう1つの重要なアプリケーションは、O(N logN)時間で配列を効率的にソートすることです。このソート手法は「ヒープソート」として知られています。

関連:挿入ソートアルゴリズムの概要

スタックにも、メモリ管理や式の評価など、さまざまな重要なアプリケーションがあります。バックトラックコーディングの問題に直面した場合は、スタックを使用して1日を節約することをお勧めします。

データ構造に優先順位を付ける

成功したプログラマーなら誰でも、データ構造に習熟することの重要性を教えてくれます。さまざまなデータ構造を理解し、必要に応じて快適に使用できるようにすることをお勧めします。これは、そこにいるすべてのプログラマーにとって重要な概念だからです。