我给出了一个数组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("%d\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;
}
最佳答案
它没有遵循从 0 到 3
索引的堆化。所以你需要堆化所有。有一些错误。如果你的数组大小是8,那么你不能超过a[8],你可以访问a[0]到a[7]
。所以你需要从0到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;
}
关于algorithm - 使用堆排序,追加数组元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61193790/