c – 混淆了两种不同的Heap实现

发布时间：2020-12-16 06:51:43 所属栏目：百科来源：网络整理

导读：功能1 void min_heapify(int arr[],int n,int i){ int j,temp; temp = arr[i]; j = 2 * i; while (j = n) { if (j n arr[j+1] arr[j]) j = j + 1; if (temp arr[j]) break; else if (temp = arr[j]) { arr[j/2] = arr[j]; j = 2 * j; } } arr[j/2] = temp;}

功能1

void min_heapify(int arr[],int n,int i){
    int j,temp;
    temp = arr[i];
    j = 2 * i;

    while (j <= n)
    {
        if (j < n && arr[j+1] < arr[j])
            j = j + 1;
        if (temp < arr[j])
            break;
        else if (temp >= arr[j])
        {
            arr[j/2] = arr[j];
            j = 2 * j;
        }
    }

    arr[j/2] = temp;
}

功能2

void max_heapify(int arr[],int i)    
{
    int largest = i;  // Initialize largest as root
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] < arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] < arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i)
    {
        swap(arr[i],arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr,n,largest);
    }
}

问题细节

这里的堆化工作方式与制作min_heap的方法相同,但问题是,我在下面的问题中使用堆来解决它,但不幸的是,我通过观看麻省理工学院的讲座实现的功能2对于这个问题没有用,看了一段时间之后在网上我找到了第一个能够无缝地解决这个问题的功能.我只是困惑他们不是同一个功能？ ——

问题

对！！问题名称反映了您的任务;只需添加一组数字.但你可能会觉得自己屈尊俯就,写一个C/C++程序只是为了添加一组数字.这样的问题只会质疑你的博学.所以,让我们为它添加一些独创性.

加法操作现在需要成本,并且成本是要添加的两者的总和.因此,要添加1和10,您需要11的成本.如果要添加1,2和3.有几种方法 –

1 + 2 = 3,cost = 3
1 + 3 = 4,cost = 4
2 + 3 = 5,cost = 5
3 + 3 = 6,cost = 6
2 + 4 = 6,cost = 6
1 + 5 = 6,cost = 6
Total = 9
Total = 10
Total = 11

我希望你已经理解了你的使命,添加一组整数,以便降低成本.

输入

每个测试用例将以正数开始,N(2≤N≤5000)后跟N个正整数(均小于100000).输入以N的值为零的情况终止.不应处理此案例.

产量

对于每种情况,在一行中打印最小的总添加成本.

SampleInput

SampleOutput

9
19

解决方法

function2中的swap函数有问题.

C是按值调用的,所以

swap(arr[i],arr[largest]);

无法交换数组中的值.

交换函数需要交换值的地址：

swap(int *v1,int *v2) {
    int tmp = *v1;
    *v1 = *v2;
    *v2 = tmp;
}

电话会是：

swap(&arr[i],&arr[largest]);

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!