1

スタックを実装して最小要素を取得するか、ヒープデータ構造を維持して最小要素を抽出するか、どちらが優れていますか。どちらも O(1) の最小要素を提供します (2 つのスタックを実装する場合、1 つは最小要素で、もう 1 つは実際の入力のスタックです)。

スタックまたはヒープを使用して最小要素または最大要素を抽出できる状況とその理由を説明してください

4

4 に答える 4

2

基本的に、2 つのスタックに基づくソリューションを使用して最小値を見つけることができますが、効果的ではなく (ヒープが N メモリを消費するのに対して 2*N メモリを消費するため)、スタックは他の目的に使用されることになっています。

于 2013-03-15T18:06:40.343 に答える
2

スタックのようなデータ構造 [1] とヒープの両方が「最小値を取得」操作をサポートしています。(メモリ割り当てに使用される「ヒープ」ではなく、ヒープ データ構造について話していることに注意してください。) どちらも新しい要素を追加することもできます。

それらは要素の削除が異なります。具体的には、スタックを使用すると、挿入とは逆の順序で要素を削除できます。ヒープを使用すると、要素を値順に削除できます (つまり、常に最小値を削除します)。

したがって、必要な操作をサポートするものを使用する必要があります。

[1] 参照されるデータ構造は、2 つの並列スタック、またはアイテムのペアのスタックのいずれかです。O(1)どちらの場合も、スタックは追加されたアイテムとその時点までの最小値の両方を保持します。これは、プッシュされたアイテムと以前の最小値の単純な最小値であるため、 で計算できます。

于 2013-03-15T18:15:56.820 に答える
0

質問がよくわかりません。

質問に似ているようです: ハンマーとジャグのどちらを使うべきですか? その答えは、何のために？

ヒープとスタックの目的/動作は異なります。

ヒープは、Insert(Key x)、GetandDeleteMin() などの API を提供します。

スタックは LIFO (後入れ先出し) API を提供しますが、Push(Value x)、Value Pop() (および必要に応じて GetMin()) です。

自問すべき質問は、min をサポートする LIFO 構造が必要かということです。その場合は、スタックを使用できます。

また

ランダムな順序で挿入し、優先度が最も高い/最も低いものを削除できる「優先度構造」が必要ですか? その場合、ヒープを使用できます。

つまり、最初に必要な動作を確認する必要があります。

実行時間とスペースの使用量を比較したこれらすべての回答は、私にも奇妙に思えます。使い方が本質的に違うのに、その比較をする意味さえあるのだろうか？最初に動作を決定し、選択できる場合は、時間/空間などの比較を行います。

あなたが本当に探しているものは何ですか？

于 2013-03-16T06:52:55.953 に答える
0

MinHeaps は、最小限の要素を非常に迅速に提供するように設計されています。最小要素を（削除せずに）覗くだけでも、O（1）（定数）時間がかかります。通常、最小限の要素を削除すると、ヒープを再ヒープ化する必要があり、log(n) 時間かかります。ウィキペディアの記事の図は MaxHeap を示していますが、MinHeap の実装はほとんど同じです。

(単一の) スタック内の最小要素を見つけるには、スタック内のすべての要素を検索して最小値を見つける必要があるため、 n時間 (および log(n) < n) かかります。したがって、pop()各要素をオフにし、記憶した最小値よりも小さいかどうかを確認し、スタック全体を通過するまで補助スタックに push() する必要があります。したがって、最小要素を取得することがデータ構造の主な目的である場合は、通常、MinHeap を使用する必要があります。

一方、他の人が参照する 2 スタック ソリューションは、操作 (add、remove、および getMin) の複雑さが O(1) ですが、removeMin の時間は O(n) です。また、最悪の場合でも 2N のスペース要件があります。

要約する：

              add/push 1    remove/pop 1   peekMin   removeMin   space
              ==========    ============   =======   =========   =====
one stack         O(1)          O(1)         O(n)       O(n)       n
two stacks        O(1)          O(1)         O(1)       O(n)      2n
minHeap         O(log(n)        N/A          O(1)     O(log n)     n

@rici が minHeap を指摘しているように、O(log n) で removeMin 操作をサポートします。つまり、スタックよりも高速ですが、追加/削除と peekMin の場合、2 スタック ソリューションの方が高速です。minHeap は、「より大きい」および「より小さい」という関係の外では、順序も維持しません。

于 2013-03-15T18:19:38.660 に答える