使用堆排序，附加一个数组元素

Question

我给出了一个数组int A[] = {12,10,9,2,11,8,14,3,5};在此数组中，前4个元素(从索引0到索引3(遵循最大堆条件。但最后5个元素(索引4到索引8(不遵循最大堆条件。因此，我必须编写一段代码，使整个数组遵循最大堆条件。

我已经给出了一个函数调用max_heap_append(A,3,8);，我必须在代码中使用它来编写程序。这是一项任务，所以我必须按照指示去做。

我在下面写了这段代码，但当我运行程序时，什么都没发生。

#include <stdio.h>
#include <stdlib.h>
void swap(int * a, int * b )
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void heapify( int A[], int q, int i) 
{
int largest = i;
int l = 2 * i + 1 ;
int r = 2 * i + 2;
if( l < q && A[l] > A[largest])
{
largest = l;
}
if( r < q && A[r] > A[largest])
{
largest = r;
}
if( largest != i)
{
swap( &A[i] , &A[largest]);
heapify(A, q, largest);
}
}

void max_heap_append(int A[], int p , int q) 
{
int i;
for( i = q / 2 -1; i >= 0; i--)  
{
heapify( A , q , i);
}
// sort the heap
for( i = q; i>= 0; i--)
{
swap(&A[0] , &A[i]);
heapify(A, i, 0);
}

}
void printA(int A[], int q)
{
int i;
for( i = 0; i <= q; i++)
{
printf("%d", A[i]);
}
printf("%dn");
}

int main()
{
int A[] = {12,10,9,2,11,8,14,3};
max_heap_append(A,3,8);
printf("Sorted: ");
printA(A, 8);
return 0;
}

Answer 1

它没有从0 to 3索引中跟随heapify。。所以你需要把一切都堆积起来。有一些错误。如果数组大小为8，则u不能超过a[8]，则可以访问a[0] to a[7]。因此您需要从0 to 7进行迭代。

试试这个：

#include <stdio.h>
#include <stdlib.h>
void swap(int * a, int * b )
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void heapify( int A[], int q, int i)
{
int largest = i;
int l = 2 * i + 1 ;
int r = 2 * i + 2;
if( l < q && A[l] > A[largest])
{
largest = l;
}
if( r < q && A[r] > A[largest])
{
largest = r;
}
if( largest != i)
{
swap( &A[i] , &A[largest]);
heapify(A, q, largest);
}
}

void max_heap_append(int A[], int p , int q)
{
int i;
for( i = q-1; i >= 0; i--)
{
heapify( A , q , i);
}
// sort the heap
for( i = q-1; i>= 0; i--)
{
swap(&A[0] , &A[i]);
heapify(A, i, 0);
}

}
void printA(int A[], int q)
{
int i;
for( i = 0; i < q; i++)
{
printf("%d ", A[i]);
}
printf("n");
}

int main()
{
int A[] = {12,10,9,2,11,8,14,3};
max_heap_append(A,3,8);
printf("Sorted: ");
printA(A, 8);
return 0;
}

Answer 2

您的代码中有几个问题

打印A

一个是/可以由编译器指示，在printA:中

printf("%d\n"(；

"%d"需要匹配的"int"参数，但没有参数

很容易猜测您只是想打印一条换行符，这样该行就可以被取代

putchar('n');

仍然在printA中，您打印没有分隔符的数字，结果不可用，例如进行

printf("%d ", A[i]);

当我在main中查看printA的调用时，参数n是A中的元素数，因此对的结束测试无效，因为您试图从数组中打印一个值，循环必须是：

for( i = 0; i < q; i++)

最大heap_append

在的第二个中，索引i可以值为0，在这种情况下，您将数组的第一个元素与其本身交换，这没有意义，对于最后两个参数值为0 的heapiy调用也是如此

当您在main中调用该函数时，参数q接收数组中的元素数量，这也是i的第一个值，仍在第二个中，用于和&数组中有一个[i]。您需要用替换该行

for( i = q-1; i> 0; i--)

如果我做了所有这些改变：

编译和执行：

bruno@bruno-XPS-8300:/tmp$ gcc -g -Wall h.c
bruno@bruno-XPS-8300:/tmp$ ./a.out
Sorted: 2 3 8 9 10 11 12 14 
bruno@bruno-XPS-8300:/tmp$