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

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-indexed。您假设代码中有 1-based 索引。
在 build_heap() 中，运行来自 [floor(n/2), 0] 的循环（您排除了第 0 个元素可能是因为上述原因）。

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

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

Can someone improve my heap data structure code?

c

heap

data-structures