An Algorithm a Day: Make a partial max heap a perfect max heap.

Introduction

   When you include some more elements in the array to the max heap, you need to still satisfy the property that the parent > children. To get this property true, we need to change the root of the tree or swap some elements(if its array) from parent to children. To simplify this operation, we use a simple induction method which is the reverse of the condition.

    Consider, parent > children is violated at index i. Also, assume that, the LEFT(i) and RIGHT(i) trees have not violated this condition yet. This is the initial condition using which we swap elements to make a perfect max heap.

Read full article from An Algorithm a Day: Make a partial max heap a perfect max heap.