次の制約を持つ「プライオリティ キュー スタック」データ構造を設計する必要があります。
- pop() と deleteMin() は、平均的なケースでは O(log(n)) で実行されます。
- push(x) と getMin() は平均時間で O(1) で実行されます
これを設計する方法について誰か提案がありますか?
2 に答える
3
これを実装するには、標準スタックを、O(1) の挿入と O(log n) の償却された削除をサポートする優先キューと組み合わせます。たとえば、スタックをフィボナッチ ヒープまたは歪んだ二項ヒープと組み合わせることができます。どちらもこれらの保証があります。O(1) 時間で 2 つの間をジャンプできるように、各スタック要素と対応する優先度キュー要素を並べるポインターを必ず格納してください。
要素をプッシュするには、スタックにプッシュし、O(1) 時間で優先キューに挿入します。最小値を読み取るには、優先度キューに O(1) 時間で最小値を問い合わせます。
最小値を削除するには、プライオリティ キューから extract-min を呼び出して最小値を削除してから、スタックに移動し、削除された要素を無効としてマークします。これには O(1) 時間かかります。ポップするには、無効とマークされていない要素をポップするまで繰り返しスタックをポップし、優先キューで delete を呼び出してその要素を削除します。これには O(k + log n) の時間がかかります。ここで、k は実行された pop の数です。ただし、潜在的な方法を使用して、これが償却された O(1) であることを示すことができます。スタックのポテンシャルを無効な引数の数に設定すると、delete-min ごとにポテンシャルが 1 ずつ増加し、k 個の無効な要素をポップするポップ操作ごとにポテンシャルが k ずつ減少します。したがって、pop の償却実行時間は O(log n) です。
お役に立てれば！
于 2013-01-16T17:18:48.853 に答える
0
最小値オブジェクトへのポイントでスタックを使用できます。したがって、その場合、push(x)、pop()、getMin() は平均時間で O(1) になります。
ただし、deleteMin() の後で、上位の項目を調整する必要があります。
于 2013-01-16T16:52:43.130 に答える