有人可以改进我的堆数据结构代码吗？

Question

我正在尝试从随机数组构建最大堆，以便我可以获得根中的最大数字。

还请建议我如何在 heapify() 函数中获取堆的大小。

#include<stdio.h>
#include<math.h>

int i;
void heapify(int a[],int i)    //n=node at which heapify needs to apply
{
    int size=8;
    int max=i,l=2i,r=2i+1;
    if(a[l]>a[max] && l<=size)
    max=l;
    if(a[r]>a[max] && r<=size)
    max=r;
    if(max==i) return;
    else
    a[max]^=a[i]^=a[max]^=a[i];
    heapify(a,max);
}

//Using this function to call recursively  heapify to maintain heap data structure
void build_heap(int arr[],int n)   //n : size of array
{
    for(i=floor(n/2);i>0;i--)    // n/2 because after that every node is a leaf node and they follow heap property by default
    {
        heapify(arr,i);
    }
}

int main()
{
    int arr[] = {2,5,4,8,9,10,3,1};
    build_heap(arr,8); 
    for(i=0;i<8;i++)
    {
            printf("%d ",arr[i]);
    }
    return 0;
}

Answer 1

除了一些更改外，您的代码似乎没问题:

• 将 2i 和 2i+1 更改为 2*i 和 2*i+1，否则您会出现编译错误。实际上它应该是 l = 2*i+1 和 r = 2*i+2 因为 C 数组是 0 索引。您假设代码中使用基于 1 的索引。
• 在 build_heap() 中，从 [floor(n/2), 0] 运行循环(您排除了第 0 个元素可能是因为上面提到的原因)。

您可以将堆的大小作为参数传递给 heapify() 函数，或将其声明为全局变量(尽管建议避免全局变量)。