ヒープ
親要素が常に2つの子要素より大きくならない(またはその逆)構造になっている。 挿入、削除がO(log n)で可能。探索は O ( n ) {\displaystyle O(n)} 。 ルートが常に最小(または最大)要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。 このときの計算量は O ( n log  n ) {\displaystyle O(n\log n)} 。(ヒープソート)
木の高さの低い方(または深さの浅い方)から、また同じ高さでも左または右のどちらかに要素を寄せた木構造を作る。深さ n {\displaystyle n} の要素がすべて使われるまで、深さ n + 1 {\displaystyle n+1} の要素は作成しない。要素の添字を 1 から開始すると、要素 n {\displaystyle n} の親は n ÷ 2 {\displaystyle n\div 2} 、子は 2 n {\displaystyle 2n} および 2 n + 1 {\displaystyle 2n+1} となる(添字を 0 から開始すると親は ( n − 1 ) ÷ 2 {\displaystyle (n-1)\div 2} 、子は 2 n + 1 {\displaystyle 2n+1} と 2 n + 2 {\displaystyle 2n+2} である)。
後述する手順に従って操作すれば、データの出現順序に関わらず、このような構造を容易に維持できることがヒープの利点である。