最大ヒープバックアップセットの効率向上

Question

最大ヒープを使用したセットでの検索の最悪の場合の時間複雑度はどのくらいですか？あなたがセット内の最小アイテムを探すなら、それはO（n）時間のオーダーを取ることができますか？より速い方法がありますか？

Answer 1

max-heapで最小の項目を見つけることは、O（n）操作です。 Min-max heapを実装すると、O（log n）の挿入と削除を維持しながら、最小のアイテムと最大のアイテムへのO（1）アクセスを提供します。ただし、全体的にmin-maxヒープは、一定の要因によってmax-heapよりも少し遅くなることに注意してください。

でmax-heapを置き換えることができます.Opt（log n）は最小の項目にアクセスできます。しかし、スキップリストを実装するのは、バイナリヒープを実装するよりも少し複雑です。おそらく、より多くのメモリを消費します。