Используя сортировку кучи, добавьте элементы массива - PullRequest
Новая
       77

Используя сортировку кучи, добавьте элементы массива

3 голосов
/ 13 апреля 2020

Я дал массив int A[] = {12,10,9,2,11,8,14,3,5}; В этом массиве первые 4 элемента (от индекса 0 до индекса 3) следуют условию максимальной кучи. Но последние 5 элементов (от индекса 4 до индекса 8) не соответствуют условию максимальной кучи. Итак, мне нужно написать код, чтобы весь массив соответствовал условию max heap.

Я дал вызов функции 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;
}

Ответы [ 2 ]

2 голосов
/ 13 апреля 2020

Его не следует heapify из 0 to 3 index .. так что вам нужно все heapify. здесь есть какая-то ошибка если ваш размер массива равен 8, то вы не можете превысить [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;
}
1 голос
/ 13 апреля 2020

У вас есть несколько проблем в вашем коде

printA

Один указывается / может указываться компилятором в printA :

printf ("% d \ n");

"% d" ожидает совпадающий аргумент int, но аргумента нет

It Легко догадаться, что вы просто хотели напечатать новую строку, чтобы эту строку можно было заменить на 

putchar('\n');

Все еще при printA вы печатаете числа без разделителя, результат не пригоден для использования Например, 

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

Когда я смотрю на вызов printA в main , параметр n - это количество элементов в A , поэтому конец теста для недопустим, поскольку при попытке вывести значение из массива значение l oop должно быть: 

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

max_heap_append

во втором для индекс i может иметь значение 0, в этом случае вы заменяете первый элемент массива на само по себе, что не имеет смысла и То же самое для вызова heapify с двумя последними аргументами, оценивающими 0

Когда вы вызываете эту функцию в main , параметр q получает число элементов в массиве, которое также является первым значением i , которое все еще находится в этой секунде для и & 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$
...