10.8 Heapify a Vector. The heapify operation converts an arrayof values into a valid max-heap form. In this lab, you'll performheapify on a vector of integers:

void heapify(std::vector &v, int &diff); // FunctionPrototype

The function takes a reference to a vector as an argument andheapifies it according to the heapify logic described below. Also,your function should calculate how many positions in the vectorchanged value as compared to the starting point. This value shouldbe returned in the diff variable.

Logic for computing the diff variable = for each position in thenew and old vector: if the positions have different value:diff++

Driver Function:

int main()
{
vector v = {20, 19, 100, 2};
int diff = 0;
heapify(v, diff);
cout << "Different in " << diff << " positions.Heap: ";
for(int i: v)
cout << i << ", ";
cout << endl;
return 0;
}

Heapify Logic: (pseudocode)

heapify() {

m = get the last used internal node index // everything after isa leaf

while( m >= 0 ) {

MaxHeapPercolateDown(m);

m--;

}

}

MaxHeapPercolateDown(nodeIndex, size) {

val = heapArray[nodeIndex]; //nodeIndex starts as 0

child_index = nodeIndex*2+1; // get first child index

while(child_index < size){

max_val = val;

max_index = -1;

for (i=child_index; i

if(heapArray[i] >max_val) {

max_val =heapArray[i];

max_index= i;

}

if (max_val == val) return; // nothingelse to do

swap(max_index,nodeIndex);

nodeIndex = max_index;

child_index = 2*nodeIndex + 1;

}

}

** Use the given logic and driver function to implement: voidheapify(std::vector &v, int &diff);