gpt4 book ai didi

algorithm - 使用堆排序,追加数组元素

转载 作者:行者123 更新时间:2023-12-04 10:13:38 27 4
gpt4 key购买 nike

我给出了一个数组 int A[] = {12,10,9,2,11,8,14,3,5};在这个数组中,第 1 个 4 个元素(从索引 0 到索引 3)遵循最大堆条件。但是最后 5 个元素(索引 4 到索引 8)不遵循最大堆条件。所以,我必须编写一个代码,以便整个数组遵循最大堆条件。

我给了一个函数调用 max_heap_append(A,3,8);我必须在我的代码中使用它来编写程序。这是一项任务,所以我必须遵循指示。

我在下面编写了这段代码,但是当我运行该程序时,没有任何 react 。

#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;
}

最佳答案

它没有跟随 heapify 来自 0 to 3索引..所以你需要堆满所有。有一些错误。如果您的数组大小为 8,那么您不能超过 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;
}

关于algorithm - 使用堆排序,追加数组元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61193790/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com