c - 删除二叉堆中的最顶层元素

Question

我正在尝试实现二进制堆。我已经成功实现了 display() 和 insert() 函数。

问题:deleteHeap() 函数内部

方法1.将堆的根复制到一个变量中

2.现在将堆的最后一个元素复制到根中。减少堆节点计数n

3.现在检查是否违反了堆的性质。

4.从顶部开始，将根节点标记为父节点。检查是否有任何子节点大于父节点。

5.将最大的 child 与 parent 交换，并将这个 child 标记为新的 parent 。

6.如果parent_index<=n/2返回；

7.否则转到第5步。

注意该程序在运行时表现异常。我建议你运行一次。!

**Code**

#include<stdio.h>
#include<stdlib.h>
int a[100],n=0;
void display()
{
    int i=1;
    printf("\nThe heap contains - ");
    while(i<=n)
        printf("%d ",a[i++]);

}
void fixheap1()
{
    int j=n,temp;//Child's index
    int i=n/2;//Parent's index
    while(a[j]>a[i] && i!=0)
    {
        temp=a[j];
        a[j]=a[i];
        a[i]=temp;

        i=i/2;
        j=j/2;
    }
}
void insert(int key)
{
    a[++n]=key;
    fixheap1();
}
int findGreatest(int j,int k)
{
    if(a[j]>a[k])
        return j;
    else 
        return k;
}
void fixheap2()
{
    int i=1,j,k,temp,max;
    while(i<=n/2)
    {
        j=2i;
        k=2i+1;
        if(k>n && j<=n)
            max=j;
        else
            if(j>n)
                break;
        else
            max=findGreatest(j,k);

        temp=a[max];
        a[max]=a[i];
        a[i]=temp;

        i=max;
    }
}
void deleteHeap()
{
    int key=a[1];
    a[1]=a[n];
    n--;
    fixheap2();
    printf("\nElement successfully deleted %d",key);
}
int main()
{

    int i,choice=0,key;
    while(choice!=5)
    {
        system("clear");
        printf("\n\t\tHeaps\n1.Insert into heap\n2.Display heap\n3.Heap sort\n4.Delete from heap\n5.Exit\n\nChoice - ");
        scanf("%d",&choice);

        switch(choice)
        {
            case 1: printf("\nEnter the number of elements to be inserted - ");
                scanf("%d",&i);
                printf("\nEnter the elements - ");
                while(i--)
                {
                    scanf("%d",&key);
                    insert(key);
                }
                printf("\nElements successfully inserted");
                break;
            case 2: display();
                break;
            case 3:
                break;
            case 4: deleteHeap();
                break;
        }

        getchar();
        getchar();
    }
    printf("\n\nThank You\n\n");
}

编辑1:有人指出错误后我已经更新了我的功能

void fixheap2()
{
    int i=1,j,k,temp,max;
    while(i<=n/2)
    {
        j=2i;
        k=2i+1;
        if(k>n && j<=n) //k does not exists
            max=j;
        else
            if(j>n) //j also doesn't exist
                break;
        else
            max=findGreatest(j,k);  //find the index of greater
        if(a[max]>a[i]) //if the child is greater than root
        {
            temp=a[max];
            a[max]=a[i];
            a[i]=temp;
            i=max;
        }
        else
            break;
    }
}

示例输入和输出:

        Heaps
1.Insert into heap
2.Display heap
3.Heap sort
4.Delete from heap
5.Exit

Choice - 1

Enter the number of elements to be inserted - 6

Enter the elements - 6 5 4 3 2 1

Elements successfully inserted


        Heaps
1.Insert into heap
2.Display heap
3.Heap sort
4.Delete from heap
5.Exit

Choice - 2

The heap contains - 6 5 4 3 2 1 


        Heaps
1.Insert into heap
2.Display heap
3.Heap sort
4.Delete from heap
5.Exit

Choice - 4

Element successfully deleted 6


        Heaps
1.Insert into heap
2.Display heap
3.Heap sort
4.Delete from heap
5.Exit

Choice - 2

The heap contains - 1 5 4 3 2 


        Heaps
1.Insert into heap
2.Display heap
3.Heap sort
4.Delete from heap
5.Exit

Choice - 4

Element successfully deleted 1

Answer 1

您的 fixheap2 没有考虑两个 child 都有效但 key 小于父项的情况。在那种情况下，堆属性已恢复，您应该停止与 child 交换(否则您将使其重新无效)。