Heapify

The 'heapify' process is a fundamental algorithm for heaps. It refers to two related concepts. The first is the procedure, often called `max_heapify` or `sift_down`, which takes a node whose subtrees are already valid heaps but which itself may violate the heap property. This procedure corrects the violation by 'sinking' the node down the tree until the heap property is restored for its subtree. This operation has a time complexity of O(log n), proportional to the height of the tree. The second, more powerful concept is using this procedure to build an entire heap from an unordered array. A naive approach would be to start with an empty heap and insert each of the n elements, taking O(n log n) time. However, a more efficient 'build-heap' algorithm exists. It starts from the last non-leaf node and calls `max_heapify` on each node, moving backwards towards the root. Since half the nodes are leaves and have no children, we only need to process the first n/2 nodes. Through careful analysis, this bottom-up approach can be shown to have a surprising linear time complexity of O(n). This efficiency makes 'build-heap' a preferred method for creating heaps, forming the basis for algorithms like Heapsort.