top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

If n elements are inserted in heap then what is the time complexity to insert n elements ?

+3 votes
269 views

A heap is constructed with n elements. Another n elements is inserted . What is the time complexity to insert n elements, please explain step by steps?

posted Nov 22, 2014 by anonymous

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button

Similar Questions
+2 votes
#include <stdio.h>
#include <stdlib.h>

void makeHeap(int heap[],int,int);
int delete(int heap[]);
int no;

int main()
{
    int heap[10],i,num,temp[10],n;

    printf("Enter the number\n");
    scanf("%d",&no);

    n=no;
    for(i=0;i<no;i++)
    {
        scanf("%d",&num);
        makeHeap(heap,num,i);
    }
    printf("The heap element are\n");

    for(i=0;i<no;i++)
        printf("%d\t",heap[i]);

    for(i=n-1;i>=1;i--)
       temp[i]=delete(heap);

    printf("\nThe sorted elements are\n");

    for(i=0;i<n;i++)
       printf("%d\t\t",temp[i]);

    return 0;
}
void makeHeap(int heap[],int data,int index)
{
    int parent,temp;
    heap[index]=data;
    while(index!=0)
    {
        parent=(index-1)/2;
        if(heap[parent]>heap[index])
        {
            temp=heap[parent];
            heap[parent]=heap[index];
            heap[index]=temp;
        }

        index=parent;

    }

}

int delete(int heap[])
{
    int i,left,min,m,c;
    int temp;
    int value=heap[0];

    heap[0]=heap[no-1];
    no--;
    i=0;

    //Problem is  coming in this while loop please help 
    while(i<no)
    {
        left=2*i+1;

        if(heap[left]<heap[i]&&left<=no)
        {
            min=left;
            temp=heap[left];
            heap[left]=heap[i];
            heap[i]=temp;

        }
        else
           min=i;

        if((heap[left+1]<heap[i])&&((left+1)<=no))
        {
           min=left+1;
            temp=heap[left+1];
            heap[left+1]=heap[i];
            heap[i]=temp;
        }
        i=min;
    }

    return value;
}
+1 vote

I am working on a android based device used for biometrics capture (iris, fingerprint, face) and some amount of local matching.

We have platform that has 2GB of memory and we want to let Android apps have large enough memory heap.

I know one can build my custom rom with build.prop with custom dalvik.vm.heapgrowthlimit, dalvik.vm.heapsize , in our experiments setting this limit to be more than 1GB causes board boot failures.

Has anybody else experimented with increasing heap size for Android application, on custom rom? I am also looking at increasing cursor window memory size as some of the biometric data is stored in sqlite
database.

Anybody else tried to wrangle Android platform to do more memory intensive applications any other places I should be looking to alter things?

...