这是我创建二进制堆的方式:
int *heapArray; // pointer to array of elements in heap
int capacity = 0; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
int d = 2;
int parent(int i)
{
return (i/d);
}
void swap(double *x, double *y)
{
double temp = *x;
*x = *y;
*y = temp;
}
double returnHeapValue(int key)
{
return heapArray[key];
}
void initialize(int cap)
{
heap_size = 0;
capacity = cap;
heapArray = (double*)malloc(cap*sizeof(double));
}
void insertJob(double x)
{
if(capacity < 10)
{
capacity = 10;
heapArray = (double*)realloc(heapArray,capacity*sizeof(double));
}
if(heap_size == capacity/2)
{
capacity += 10;
heapArray = (double*)realloc(heapArray,capacity*sizeof(double));
}
heap_size = heap_size + 1;
heapArray[heap_size] = x;
maxHeapSwim(heap_size);
}
void maxHeapSwim(int k)
{
while(k > 1 && heapArray[parent(k)] < heapArray[k] && k!=1)
{
swap(&heapArray[k],&heapArray[parent(k)]);
k = parent(k);
}
}
这是我在 main 方法中插入一堆双打然后打印出来所做的:
int main()
{
// test
initialize(20);
insertJob(2.0);
insertJob(3.0);
insertJob(1.0);
insertJob(6.0);
insertJob(4.0);
insertJob(14.0);
insertJob(7.0);
insertJob(9.0);
insertJob(8.0);
insertJob(11.0);
printf("n");
printf("%f", returnHeapValue(1));
printf("n");
printf("%f", returnHeapValue(2));
printf("n");
printf("%f", returnHeapValue(3));
printf("n");
printf("%f", returnHeapValue(4));
printf("n");
printf("%f", returnHeapValue(5));
printf("n");
printf("%f", returnHeapValue(6));
printf("n");
printf("%f", returnHeapValue(7));
printf("n");
printf("%f", returnHeapValue(8));
printf("n");
printf("%f", returnHeapValue(9));
printf("n");
printf("%f", returnHeapValue(10));
printf("n");
return 0;
}
但是,输出如下所示:
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
为什么数字没有正确打印?我做错了什么吗?当我使用整数值对其进行测试时,一切正常。但是当我尝试插入"双精度"数据类型的值时,它不起作用。
编辑:
我还尝试将 heapArray 的类型从 int 更改为 double,如下所示:
double *heapArray;
不幸的是,这会导致我创建的另一个函数出错:
double delMaxPriorityJob() //This function deletes the largest value (in the root)
{
double max = heapArray[1];
swap(&heapArray[1],&heapArray[heap_size]);
heap_size = heap_size - 1;
maxHeapSink(1);
heapArray[heap_size + 1] = NULL; //The error is in this line
return max;
}
错误说:
"从类型'void *'分配给类型'双精度'时不兼容的类型"
我修复了它。问题是,我正在尝试从不同的类运行main()函数。它以前不起作用的原因是我没有在二进制堆的头文件中正确指定函数。这是头文件现在的样子:
extern void initialize(int cap);
extern void resetHeap();
extern int count_heap_elements();
extern int returnHeapCapacity();
extern double returnHeapValue(int key);
extern void insertJob(double x);
extern void insertEvent(double x);
extern double delMaxPriorityJob();
extern double delMaxPriorityEvent();
extern void maxHeapSink(int k);
extern void maxHeapSwim(int k);
extern void minHeapSwim(int k);
extern void minHeapSink(int k);
现在,当我从不同的类运行该 main() 函数时,我得到了正确的输出。