我正在尝试从随机数组构建最大堆,以便我可以获得根中的最大数字。
还请建议我如何在 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;
}
最佳答案
除了一些更改外,您的代码似乎没问题:
- 将
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()
函数,或将其声明为全局变量(尽管建议避免全局变量)。
关于有人可以改进我的堆数据结构代码吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39062063/