Confused с двумя различными реализации Heap

Question

Функция 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); 
    } 
} 

Проблема Детали

Здесь heapification работают точно так же, чтобы сделать min_heap, но проблема в том, что я использовал кучу в этом ниже probl чтобы решить эту проблему, но, к сожалению, функция 2, которую я реализовал, наблюдая за лекцией MIT, не помогла решить эту проблему, после некоторого времени в Интернете я нашел 1-ю функцию, которая без проблем работала над этой проблемой. Я просто смущен, разве это не одна и та же функция? ------

Проблема

Да !! Название проблемы отражает вашу задачу; просто добавьте набор чисел. Но вы можете почувствовать себя снисходительным, написать программу 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  

SampleOutput

9 
19 

Answer 1

Ok я узнаю решение была допущена ошибка при проверке состояния , в условии if, где мы проверяем, что if (осталось < = n), это было ранее (осталось < n), поэтому он не работал для этой проблемы. Спасибо.

void min_heapify(int arr[],int n, int i){  
    int lowest = i; // Initialize lowest as root 
    int left = 2*i ; 
    int right = 2*i + 1; 



// If child is lower than root 
    if(left <= n && arr[left] < arr[lowest]){ 
     lowest = left; 
    } 

    // If right child is lower than lowest 
    if(right <= n && arr[right] < arr[lowest]){ 
     lowest = right; 
    } 
    // If lowest is not root 
    if(lowest != i){ // also break condition 
     swap(arr[i], arr[lowest]); 

     //Recursively heapify 
     min_heapify(arr, n, lowest); 

    } 

Answer 2

Существует проблема с swap функции в function2.

С вызова по значению, так что

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

не может поменять значения в массиве.

Функция замены нужны адреса значений для замены:

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

И призыв будет:

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