Как реализовать кучу с рекурсией - PullRequest
Новая
       13

Как реализовать кучу с рекурсией

0 голосов
/ 09 апреля 2020

Я пытался реализовать кучу (это максимальная куча) с рекурсией на "C" , но проблема в том, что я не получаю соответствующий вывод из него: В приведенном ниже коде функция insert принимает в качестве аргумента входные данные и адрес массива, который создается для кучи, а затем проверяет, являются ли данные больше, чем его родительский узел, или нет. оказывается больше, чем он заменяет меньшее значение, помещаемое в индекс родительского элемента, на более высокое значение, помещаемое в индекс данных, и повторяет процесс до тех пор, пока не будет удовлетворено свойство максимальной кучи или пока он не достигнет root, Здесь индекс родителя представлен как heap[i-1]/2, а индекс вновь добавленных данных просто "i" т.е. heap[i] Предположим, что я ввел 20 и после этого, если я введу большее значение, такое как 30 , тогда результат будет 30 20 , но вместо этого я получу вывод только как 30 * 10 21 * и если решите добавить другое большее значение (скажем, 40), то оно заменит 30 , и на выходе получится только 40 . вот код -> 

int i = 0;
void insert(int heap[],int data)
{
    int j = 0;
    if(i == 0)
        {
            heap[i] = data;
        }
        else if(heap[(i-1)/2] < data)
        {
            heap[i] = heap[(i-1)/2];
            i = (i-1)/2;
            insert(heap,data);

        }
}
void display(int heap[],int size)
{
    system("cls");
    for(int i=0,j=1;i<size;i++,j++)
    {
        printf("%d.) %d\n",j,heap[i]);
    }
}

void main()
{
    int heap[5],men,data,c;
    while(1)
    {
        system("cls");

        printf("1.) Insert\n");
        printf("2.) Display\n");
        printf("3.) exit\n");
        printf("Enter your choice : ");
        scanf("%d",&men);
        switch(men)
        {
            case 1 : printf("Enter data : ");
                     scanf("%d",&data);
                     heap[i] = data;
                     insert(heap,data);
                     i++;
                     printf("%d successfully added to heap!",data);
                     break;

            case 2 : display(heap,i);
                    break;

            case 3 : exit(0);
            break;

            default : printf("Invalid choice!");
                      while((c=fgetc(stdin))!='\n'){}
                      break;            
        }
        getch();
    }

}

1 Ответ

1 голос
/ 10 апреля 2020

Проблема с вашим методом insert состоит в том, что вы никогда ничего не добавляете в массив, кроме случаев, когда i==0.

Алгоритм добавления элемента в минимальную кучу: 

Add new item to the end of the array.
While the new item is smaller than its parent
    swap new item with parent item

Переведен в псевдокод и немного оптимизирован, что становится: 

count = count + 1
i = count - 1
parent = (i-1)/2
while (data < a[parent])
    a[i] = a[parent])
    i = parent
    parent = (i-1)/2
a[i] = data

Рекурсивная версия почти такая же.

Ваш код никогда не увеличивает количество, поэтому куча не может расти.

...