如何使用递归实现堆

Question

我一直在尝试用“ C”语言进行递归实现堆（这是最大堆），但是问题是我没有从代码中获得适当的输出， insert函数下面的内容将输入数据和为堆创建的数组的地址作为参数，然后检查数据是否大于其父节点，以及数据是否大于其父节点。将放置在父级索引上的较小值替换为放置在数据索引上的较高值，并重复该过程，直到满足最大堆的属性或到达根为止。父级表示为heap[i-1]/2，而新添加的数据的索引仅为“ i”，即heap[i]假设我输入了20，然后如果我输入了一个较大的值，例如30，那么输出应该是3020，但是我只能以30的形式获得输出，如果决定添加另一个更大的值（例如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();
    }

}

Answer 1

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

递归版本几乎相同。

您的代码永远不会增加计数，因此堆不会增长。