Si la position du nœud est connue, decrease-key dans un tas binaire coûte :

Θ
(
1
)
Θ(1) au mieux si aucune restauration n’est nécessaire ;

Θ
(
log
⁡
𝑛
)
Θ(logn) au pire, car le nœud peut parcourir toute la hauteur du tas.

Dans un tas-min, la clé diminuée remonte par sift-up. Dans un tas-max, elle peut descendre par sift-down. Sans position connue, la recherche de l’élément peut coûter 
𝑂
(
𝑛
)
O(n).