ヒープへの追加

ウィキペディア小見出し辞書

ヒープへの追加

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/03 14:40 UTC 版)

「二分ヒープ」の記事における「ヒープへの追加」の解説

すでに存在しているヒープに、前述の制約を保ったまま要素を追加するには、up-heap（bubble-up, percolate-up, sift-up, trickle-up, heapify-up, cascade-up 等とも）と呼ばれる操作によらなければならない。以下のアルゴリズムにしたがって、二分ヒープに対し O(log n) で操作を行うことができる。 ヒープの最下層に要素を追加する 追加した要素とその親を比較する。正しい順序で並んでいるならば、停止する。 もし順序が正しくないならば、親と追加要素を交換して、2に戻る。 この操作は、木上で最大各々の深さで行う必要がある。つまり、木の高さ分行う必要があるので、O(log n) かかる。しかしながら、およそ要素の50%が葉であり最下層から2レベルまでには75%の要素が含まれることから、新しい要素を挿入する際、ヒープを維持するために、上向きに2, 3レベル動かすくらいですむだろう。このように、二分ヒープは、要素の挿入には平均 O(1) の固定時間をサポートする。 最大ヒープと呼ばれるのは以下のようなものである。 ここで、ヒープに「15」という数字を付け加えたい。まず最初に X の印がついている場所に「15」を置く。しかし、「15」は親である「8」より大きいのでヒープの制約条件に違反している。そこで、「15」と「8」を入れ替える。最初の入れ替え後、ヒープは以下の様になる。 しかし「15」はその親である「11」よりも大きいので、まだヒープの制約条件に違反している。そこで、再度入れ替える必要がある。 これで、適切な最大ヒープができた。