sift up (original) (raw)

(algorithm)

**Definition:**Restoring the heap property by swapping a node with its parent, and repeating the process on the parent until the root is reached or the heap property is satisfied.

Note: Insertion in a binary heap is implemented by adding a node to the end of of the array and then performing a "sift up" starting at that node. After LK.

Author: PEB

More information

An illustration of sift up.

Go to theDictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 6 April 2023.
HTML page formatted Wed Oct 30 12:15:31 2024.

Cite this as:
Paul E. Black, "sift up", inDictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 April 2023. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/siftup.html