I am currently learning about heap sort and I am having trouble understanding the heapify process, particularly when both children of the root are larger than the root itself, and the sub-children (children of the children) are also larger than their parents.

Consider the following initial max-heap structure:

Intial Structure

    2
   / 
  3   4
 /  / 

12 8 9 10

When the heapify process is applied to the root node (value 2), the following steps should occur:

1. Compare the root (2) with its children (3 and 4).
2. Swap the root with the largest child (4), resulting in

Structure after Heapify process is applied

    4
   / 
  3   2
 /  / 

12 8 9 10

Recursively heapify the subtree rooted at the swapped node (value 2):

1. Compare 2 with its children (9 and 10).
2. Swap 2 with the largest child (10), resulting in

structure after Recursively heapify

    4
   / 
  3   10
 /  / 

12 8 9 2

However, the final structure seems incorrect because the parent node (4) is now smaller than one of its children (10). I am confused about how the heapify process ensures the max-heap property is maintained in such scenarios. Could someone explain the correct steps and logic behind heapify in this context?

I followed the standard heapify process to maintain the max-heap property.

I was expecting the heapify process to correctly maintain the max-heap property throughout the heap. Specifically, I anticipated that after the heapify calls, every parent node would be greater than or equal to its children.

However, the final structure appears to violate the max-heap property, as the node with value 4 is smaller than its child with value 10. This confusion led me to question whether I correctly understood the heapify process, especially when both children and their sub-children are larger than the root.

I am expecting someone to explain how the heapify process correctly maintains the max-heap property in this scenario.