データ構造: ヒープ

ヒープは、要素を優先度順に整理した線形データ構造で、最大の要素が常に先頭に配置されます。完全2分木として表され、ヒープでは、各親ノードは子の優先度よりも高い優先度を持つことが保証されます。 選択、挿入、削除などの操作は、木の上下に移動して順序を維持するために、O(log n)の複雑さがあります。優先度の変更もまたO(log n)の複雑さがあります。 「上昇」アルゴリズムは、要素の優先度が親よりも高い場合に、その要素を木の中で上に移動します。「下降」アルゴリズムは、要素の優先度が子よりも低い場合に、その要素を木の中で下に移動します。 挿入には、新しい要素を最後に追加し、順序を維持するために木の中で上に移動させることが含まれます。最も優先度の高い要素の削除には、それを最後尾の要素に置き換え、順序を維持するためにその要素を下に移動させることが含まれます。 ヒープは、リストをソートする(O(n log n))か、木の内部ノードをリストの半分から降順させる(O(n))ことで構築できます。