如何用递归实现堆

Question

我一直在尝试用 "C" 语言递归实现堆（这个是最大堆）但是问题是我没有从中得到适当的输出，在下面的代码中，insert 函数将输入数据和为堆创建的数组地址作为参数，然后检查数据是否正确大于或不大于它的父节点，如果数据结果大于它那么它用放置在数据索引上的较高值替换放置在父节点索引上的较小值并重复该过程直到满足最大堆的属性或者到达根，这里parent的索引表示为heap[i-1]/2，新增数据的索引就是"i"即heap[i] 假设我输入 20 之后，如果我输入一个更大的值，如 30 那么输出应该是 30 20 但我只得到 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

递归版本几乎相同。

您的代码从不增加计数，因此堆无法增长。

如何用递归实现堆

How to implement heap with recursion

c

arrays

heap

recursion