c - Build a binary-heap from an array, which method is more efficient and why -

i learning heaps , have found 2 ways of building them given array: trying build max heap.

1.top down approach

here check every element if @ correct position or not. using method called restoreup, in every key compared parent key , , if parent key smaller parent key moved down.this procedue continues till parent key greater.i check every key starting @ index position 2.

my code is:

void restoreup(int arr[],int i) {     int k=arr[i];     int par=i/2;     while(arr[par]<k)     {         arr[i]=arr[par];         i=par;         par=i/2;     }     arr[i]=k; } void buildheap1(int arr[],int size) {     int i;     for(i=2;i<=size;i++)        restoreup(arr,i); }  

1. bottom approach

here start first non leaf node present @ index floor(size/2), , call method restoredown until node number 1.i compare key both left , right child , greater child moved up.if both children greater key move larger of 2 children up.this procedure stops when both children smaller key.

my code is:

void restoredown(int arr[],int i,int size) {     int left=2*i;     int right=2*i+1;     int num=arr[i];     while(right<=size)     {         if(num>arr[left] && num>arr[right])         {             arr[i]=num;             return;         }         else if(arr[left]>arr[right])         {             arr[i]=arr[left];             i=left;         }         else         {             arr[i]=arr[right];             i=right;         }         left=2*i;         right=2*i+1;     }     if(left==size && arr[left]>num)     {         arr[i]=arr[left];         i=left;     }     arr[i]=num; } void buildheap2(int arr[],int size) {     int i;     for(i=size/2;i>=1;i--)        restoredown(arr,i,size); } 

both methods working me. wanted know method more efficient , why?

generally speaking modern cpu (having caches). reading , array backward bad idea generates lot of cache misses. unless (of course) array in cache.

so first approach seems better point of view.