(algorithm)
Definition: Rearrange a heap to maintain the heap property, that is, the key of the root node is more extreme (greater or less) than or equal to the keys of its children. If the root node's key is not more extreme, swap it with the most extreme child key, then recursively heapify that child's subtree. The child subtrees must be heaps to start.
Aggregate parent (I am a part of or used in ...)
heapsort.
See also binary heap, build-heap.
Note: For an array implementation, heapify takes O(log2 n) or O(h) time under the comparison model, where n is the number of nodes and h is the height.
Author: PEB
An illustration of heapify.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 6 April 2023.
HTML page formatted Fri Apr 7 09:27:46 2023.
Cite this as:
Paul E. Black, "heapify", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 April 2023. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/heapify.html