堆中的路径需要太长时间

Question

这是oj的问题PAT

Insert a sequence of given numbers into an initially empty min-heap H. Then for any given index i, you are supposed to print the path from H[i] to the root.

但是，我的代码总是超时，即花费的时间太长。如何解决？

main()
{
    int i,*a,n,m,k,data;
    scanf("%d%d",&n,&m);
    a=malloc(n*sizeof(int));
    a[0]=-10001;  //
    for(i=1;i<=n;i++)
    {
        scanf("%d",&data);
        heapAdjust(a,data);
    }   

    for(i=1;i<=m;i++)
    {
        scanf("%d",&k);
        printf("%d",a[k]);
        k=k/2;
    while(1)
    {
        printf(" %d",a[k]);
        if(k==1)
            break;
        k=k/2;
    }
    printf("\n");
    }
    free(a);
}
void heapAdjust(int a[],int data) // make heap
{
    static int size=0;
    int i;
    i=++size;
    for(;a[i/2]>data;i=i/2)
        a[i]=a[i/2];
    a[i]=data;
}

Answer 1

您可能运行陷入无限循环，因为 k 在某个时刻变为零。

尝试将 while(1) 循环内的 break 条件从 k == 1 更改为 k <= 1，看看是否有帮助。

堆中的路径需要太长时间

Path in a Heap takes too long time

c

heap

data-structures