A binary heap is a complete binary tree which satisfies the heap property. For a max-heap, this property is:
For every node 𝑖, the value of 𝑖 is greater than or equal to the values of its children.
Formally, if 𝐴A is an array representation of the heap and 𝑖i is a node, then:
𝐴[𝑖]≥𝐴[2𝑖+1] and 𝐴[𝑖]≥𝐴[2𝑖+2]
(assuming a 0-based array indexing).
To prove that the root of any subtree in a max-heap contains the largest value in that subtree, let's consider a node 𝑖 in the max-heap and the subtree rooted at 𝑖.
According to the max-heap property, for the root node 𝑖,
𝐴[𝑖]≥𝐴[2𝑖+1] and 𝐴[𝑖]≥𝐴[2𝑖+2]
This means 𝐴[𝑖] is greater than or equal to its immediate children.
Since the subtree rooted at any child of 𝑖 is also a max-heap, the root of these subtrees will be greater than or equal to all their respective children. Thus, by recursive application of the heap property:
𝐴[2𝑖+1]≥all descendants of 2𝑖+1
𝐴[2𝑖+2]≥all descendants of 2𝑖+2
Thus, A[i]≥all descendants of i
Thus, the root of any subtree in a max-heap contains the largest value occurring anywhere in that subtree.
Comments