2
\$\begingroup\$

I am learning about heaps, and I have found two ways of building them from a given array: I am trying to build up a MAX Heap.

1. Top-down approach

Here I check for every element to see if it is at the correct position or not. By using a function called restoreUp, in which every key is compared to its parent key, and if the parent key is smaller than the parent key is moved down. This procedure continues until the parent key is greater. I check it for every key starting at 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);
} 

2. Bottom-up approach

Here I start from the first non-leaf node present at index floor(size/2), and call a function restoreDown until node number 1. I compare a key with both its left and right child and then the greater child is moved up. If both children are greater than the key, then I move the larger of the two children up. This procedure stops when both children are smaller than the 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 the methods are working for me. Which method is more efficient and why?

\$\endgroup\$
4
\$\begingroup\$

Someone with more expertise on algorithms may provide a more concrete answer to your specific algorithms. However, I would like to point out two things on a general note:

1. Do the math.

Mathematically determining the complexity of an algorithm usually isn't that hard. Calculate big-O, check number of operations for given inputs and so on. While the answer may not be extremely precise, it's a nice exercise and can be very helpful.

2. Measure twice; cut once.

The best way to figure out the speed of an algorithm is to run it. Calculating the theoretical complexity is useful, but doesn't account for cache misses, branch prediction and the plethora of other things that can affect the execution speed. Run your algorithm on a large number of inputs and test cases to get statistically significant results. Run with and without a profiler to measure what exactly takes time. Sometimes you will find that altering the input, for example by sorting it or changing its layout to reduce cache misses, is more effective than altering the algorithm.

\$\endgroup\$
  • \$\begingroup\$ Sorting the input array in descending order does the job, as each node of the heap is earlier in the array that both its children. However, a heap needs a partial order only, so imposing a linear order with sorting the array may turn out both overkill and waste of time, as sorting may take O(n log n) time, while bottom-up heapifying takes O(n) only (Wikipedia: Binary heap § Building a heap). \$\endgroup\$ – CiaPan Jun 12 '18 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.