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

Question

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

问题：deleteHeap()函数内部

方法 1.Copy 堆的根变成一个变量

2.Now复制堆的最后一个元素到root.Decrement堆节点数n

3.Now检查堆的属性是否被侵犯

4.Start 从 top.Mark 根节点作为 parent 节点。检查是否有任何 children 大于 parent 节点。

5.Swap 最大的 child 和 parent 并将此 child 标记为新的 parent。

6.If parent_index<=n/2 return;

7.Else 转到步骤 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 没有考虑 children 都有效但密钥小于 parent 的情况。在那种情况下，堆属性已经恢复，你应该停止与 children 交换（否则你会 re-invalidate 它）。

Answer 2

@Sneftel 已经在上面指出了第一个错误

好的！我注意到程序中有一个小错误被编译器忽略并且不容易被发现。

在编辑 1 部分

j=2i
k=2i+1

显然 2i 未被评估为 2*i 这很明显，因为我们正在用 c 编写代码，但有趣的是它被评估为零。

虽然这是一个愚蠢的错误。

所以如果我有一个程序

int main()
{
    int i=21,j,k;
    j=2i+1;
    k=2i;
    printf("\n%d\n%d\n",j,k);
}

输出将是

1
0

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

Deleting the topmost element in the binary heap

c

arrays

heap