Путать с двумя различными реализациями кучи

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, но проблема в том, что я использовал кучу в этой задаче ниже, чтобы решить ее, но, к сожалению, функция 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

SampleOutput

9
19

4

arrays c++min-heap

Решение

Другие решения

Хорошо, я обнаружил, что решение было ошибкой в проверке условия, в условии if, где мы проверяли, что (оставлено) <= 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);

}

0

Источник

Accepted Answer

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

C является вызовом по значению, поэтому

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

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

Для функции подкачки требуются адреса значений для подкачки:

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

И звонок будет:

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

0