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

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("%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;
}

Answer 1

它没有从 0 to 3 索引中跟随 heapify.. 所以你需要全部堆化。有一些错误。如果你的数组大小是 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;
}

Answer 2

你的代码有几个问题

printA

一个 is/can 由编译器指示，在 printA :

printf("%d\n");

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

很容易猜到你只是想打印一个换行符，所以该行可以替换为

putchar('\n');

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

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

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

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

max_heap_append

在第二个 for 中，索引 i 可以取值为 0，在这种情况下，您将数组的第一个元素与其自身交换，这对于 heapify 的调用没有任何意义，最后 2 个参数的值为 0

当您在 main 中调用该函数时，参数 q 接收数组中元素的数量，这也是第一个值i 的 for 和 &A[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$

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

Using heap sort, append an array elements

algorithm

data-structures

heap

heapsort

max-heap