heapifyup

Heapifyup is a procedure used in heap data structures to restore the heap property after inserting a new element. It can also be used when a key becomes more extreme in a heap, such as increasing a key in a max-heap or decreasing a key in a min-heap.

In a binary heap implemented with an array, a new element is appended at the end, and heapifyup compares the element with its parent. If the heap property is violated (for a max-heap, the element is greater than its parent; for a min-heap, it is smaller than its parent), the two are swapped. The process repeats with the new position until the root is reached or the heap property holds.

Indexing details: with 0-based indexes, the parent of index i is floor((i-1)/2); with 1-based indexes, the parent is floor(i/2). The time complexity is O(log n) in the height of the heap; space usage is O(1) beyond the stored data. Heapifyup is typically invoked after insertion and, depending on the operation, when a key changes in a way that could violate the heap property. It is also known as sift-up or bubble-up in some implementations.