sift-up and sift-down

The two heap repair operations: sift-up moves a new item up past larger parents, and sift-down moves a displaced root down past smaller children.

In more detail

After an append, sift-up swaps with the parent until the heap property holds. After the root is removed and replaced by the last item, sift-down swaps with the smaller child until it holds. Each walks one root-to-leaf path, so each costs O(log n).

Related terms

Taught in

References