バイナリヒープとプライオリティキュー

Question

ヒープとバイナリヒープの新機能です。なぜバイナリヒープを使用してプライオリティキューを実装する必要があるのか​​理解しようとしています。私はまた、バイナリヒープの基礎となるデータ構造が配列であることを理解しています。

私の質問は、優先順位キューを表すために降順（最大ヒープ用）または昇順（最小ヒープ用）の順序でソートされた配列を使用できないことです。私はここで間違っているかもしれませんが、findMax、findMin、insert、deleteのような操作の時間の複雑さは、このように実装されていればほとんど同じであると思います。優先順位キューを表すためにソートされた配列を使用することはできませんか？

私はすでに、この答えを読んでいる：Heap vs Binary Search Tree (BST)

Answer 1

あなたはプライオリティキューを表すために、配列を使用することができますが、あなたがそうするとき、あなたは効率の多くを失います。配列に何かを挿入し、キュー内のオブジェクトより優先度が高いとします。インデックス0に移動する必要があり、インデックス0にあるオブジェクトはインデックス1に移動する必要があります。

これはO（n）ですが、バイナリツリーで構成されるプライオリティキューの先頭に値を挿入すると、lg（n）ノードを変更するだけで、バイナリツリーをモデリング優先キュー配列よりも。

要素の削除は、同様の時間の複雑さを持ちます。

優先度キューの後ろにアクセスするのは、配列で実装されている場合は一定時間ですが、バイナリツリーで実装されている場合はO（n）時間なので、配列はバイナリツリーよりも大きな利点ですが、多くの場合、最も優先順位の低い要素にアクセスする必要はないため、バイナリツリーは一般的な配列よりも効率的に優先順位のキューを表します。