c++ - 混淆了堆的两种不同实现

功能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 n, 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的方法相同，但是问题是，我在下面的问题中使用了堆来解决它，但是不幸的是，在看了一段时间之后，我通过观看MIT讲座实现的函数2不适用于该问题。在网络上，我找到了第一个功能，可以无缝解决此问题。我只是感到困惑，是不是它们具有相同的功能？ ------

问题

是的!!问题名称反射(reflect)了您的任务；只需添加一组数字即可。但是您可能会觉得自己屈尊了，编写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

3
1 2 3
4
1 2 3 4
0

示例输出

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]);