二分ヒープ
すでに存在しているヒープに、前述の制約を保ったまま要素を追加するには、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」よりも大きいので、まだヒープの制約条件に違反している。そこで、再度入れ替える必要がある。

これで、適切な最大ヒープができた。