= Sift down
= Heapify down
{synonym}
To repair a key in a minimum-oriented <binary heap>, choose the smaller-priority present entry among its <children in a rooted tree>. Exchange if that entry is smaller than the moving key, and continue at the new index. Stop when there are no <children in a rooted tree> or the <heap order> holds. The smaller <rooted trees> below the starting entry must already obey the <heap order>; choosing the larger child could leave a violation with the smaller one.
Back to article page
