0

我正在使用一种简单的方法以自下而上的方式将数组转换为堆。我找不到错误。有人可以看看，让我知道。

基本上我是以自下而上的方式制作一个随机数组。

for(int i=n/2;i>=1;i--)
        {
                    heapify(i,n,arr);
        }

heapify 程序存在一些问题，有时会给出正确的结果，但大多数时候是错误的。

`#include<iostream>
#include<conio.h>
using namespace std;
int min(i
nt x,int y,int z)
{
    return ((x>y?x:y)>z?(x>y?x:y):z);
}
int left(int i)
{
    return (2*i);enter code here
}
int right(int i) 
{
    return (2*i+1);
}
int parent(int i)
{
    return (i/2);
}
int heapify(int i,int n,int arr[])
{
    int temp;
    int l=left(i);
    int r=right(i);
    temp=i;
    if(l<=n&&arr[l]<arr[i])
    temp=l;
    else if(r<=n&&arr[temp]>arr[r])
    temp=r;
    if(temp!=i)
    {
               int x=arr[temp];
               arr[temp]=arr[i];
               arr[i]=x;
               heapify(temp,n,arr);
    }   
    //else return 0;
}
int deletemin(int n,int arr[])
{
               cout<<arr[1]<<"\ndeLeted\n";   
               arr[1]=arr[n];

}
int insert(int x,int size,int arr[])
{
    arr[size]=x;
    int i=(size);
    do
    {
    i=parent(i);
    if(arr[i]!=min(arr[i],arr[left(i)],arr[right(i)]))
    heapify(i,(size),arr);
    else
    return 0;
    }while(i!=1);
}

int main()
{
    int n,t,arr[100];
    cin>>t;
    while(t--)
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    for(int i=n/2;i>=1;i--)
    {
                heapify(i,n,arr);
    }
    for(int i=1;i<=n;i++)
    cout<<arr[i]<<" ";
    deletemin(n,arr);
    n--;
    heapify(1,n,arr);
    for(int i=1;i<=n;i++)
    cout<<arr[i]<<" ";
    int y;
    cout<<"what value do you want to insert\n";
    cin>>y;
    n++;
    insert(y,n,arr);
    for(int i=1;i<=n;i++)
    cout<<arr[i]<<" ";

    }

    getch();
    return 0;
}

`
4

1 回答 1

0

一个简单的观察是你的 min 函数是错误的！它不返回 3 个数字的最小值。暂时用 ifs 来做吧！

于 2012-07-08T11:08:07.243 回答