Соединяйте н веревки с минимальными затратами

// C ++ программа для соединения n веревок с минимальными затратами
#include <iostream>

using namespace std;

  
// Min Heap: Коллекция узлов min heap

struct MinHeap {

    unsigned size; // Текущий размер кучи мин

    unsigned capacity; // емкость мин кучи

    int* harr; // Присоединение узлов minheap

};

  
// Утилита для создания минимальной кучи заданной емкости

struct MinHeap* createMinHeap(unsigned capacity)

{

    struct MinHeap* minHeap = new MinHeap;

    minHeap->size = 0; // текущий размер равен 0

    minHeap->capacity = capacity;

    minHeap->harr = new int[capacity];

    return minHeap;

}

  
// Вспомогательная функция для замены двух минимальных узлов кучи

void swapMinHeapNode(int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Стандартная функция minHeapify.

void minHeapify(struct MinHeap* minHeap, int idx)

{

    int smallest = idx;

    int left = 2 * idx + 1;

    int right = 2 * idx + 2;

    if (left < minHeap->size && minHeap->harr[left] < minHeap->harr[smallest])

        smallest = left;

    if (right < minHeap->size && minHeap->harr[right] < minHeap->harr[smallest])

        smallest = right;

    if (smallest != idx) {

        swapMinHeapNode(&minHeap->harr[smallest], &minHeap->harr[idx]);

        minHeapify(minHeap, smallest);

    }

}

  
// Утилита для проверки, если размер кучи равен 1 или нет

int isSizeOne(struct MinHeap* minHeap)

{

    return (minHeap->size == 1);

}

  
// Стандартная функция для извлечения узла минимального значения из кучи

int extractMin(struct MinHeap* minHeap)

{

    int temp = minHeap->harr[0];

    minHeap->harr[0] = minHeap->harr[minHeap->size - 1];

    --minHeap->size;

    minHeapify(minHeap, 0);

    return temp;

}

  
// Вспомогательная функция для вставки нового узла в Min Heap

void insertMinHeap(struct MinHeap* minHeap, int val)

{

    ++minHeap->size;

    int i = minHeap->size - 1;

    while (i && (val < minHeap->harr[(i - 1) / 2])) {

        minHeap->harr[i] = minHeap->harr[(i - 1) / 2];

        i = (i - 1) / 2;

    }

    minHeap->harr[i] = val;

}

  
// Стандартная функция для построения минимальной кучи

void buildMinHeap(struct MinHeap* minHeap)

{

    int n = minHeap->size - 1;

    int i;

    for (i = (n - 1) / 2; i >= 0; --i)

        minHeapify(minHeap, i);

}

  
// Создаем минимальную кучу емкости, равную размеру, и вставляем все значения
// из len [] в нем. Первоначально размер минимальной кучи равен емкости

struct MinHeap* createAndBuildMinHeap(int len[], int size)

{

    struct MinHeap* minHeap = createMinHeap(size);

    for (int i = 0; i < size; ++i)

        minHeap->harr[i] = len[i];

    minHeap->size = size;

    buildMinHeap(minHeap);

    return minHeap;

}

  
// Основная функция, которая возвращает минимальную стоимость для подключения n веревок
// длины сохраняются в len [0..n-1]

int minCost(int len[], int n)

{

    int cost = 0; // Инициализировать результат

    // Создаем минимальную кучу емкости, равную n, и помещаем в нее все веревки

    struct MinHeap* minHeap = createAndBuildMinHeap(len, n);

    // Итерация, пока размер кучи не становится 1

    while (!isSizeOne(minHeap)) {

        // Извлекаем две веревки минимальной длины из минимальной кучи

        int min = extractMin(minHeap);

        int sec_min = extractMin(minHeap);

        cost += (min + sec_min); // Обновить общую стоимость

        // Вставляем новую веревку в кучу мин с длиной, равной сумме

        // из двух извлеченных минимальных длин

        insertMinHeap(minHeap, min + sec_min);

    }

    // Наконец, возвращаем итоговую минимальную стоимость для соединения всех веревок

    return cost;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int len[] = { 4, 3, 2, 6 };

    int size = sizeof(len) / sizeof(len[0]);

    cout << "Total cost for connecting ropes is " << minCost(len, size);

    return 0;

}

// Java-программа для соединения n веревок с минимальными затратами

  
// Класс для Min Heap

class MinHeap {

    int[] harr; // Массив элементов в куче

    int heap_size; // Текущее количество элементов в мин куче

    int capacity; // максимально возможный размер кучи min

    // Конструктор: строит кучу из

    // заданный массив a [] заданного размера

    public MinHeap(int a[], int size)

    {

        heap_size = size;

        capacity = size;

        harr = a;

        int i = (heap_size - 1) / 2;

        while (i >= 0) {

            MinHeapify(i);

            i--;

        }

    }

    // Рекурсивный метод для подкачки поддерева

    // с корнем по заданному индексу

    // Этот метод предполагает, что поддеревья

    // уже куча

    void MinHeapify(int i)

    {

        int l = left(i);

        int r = right(i);

        int smallest = i;

        if (l < heap_size && harr[l] < harr[i])

            smallest = l;

        if (r < heap_size && harr[r] < harr[smallest])

            smallest = r;

        if (smallest != i) {

            swap(i, smallest);

            MinHeapify(smallest);

        }

    }

    int parent(int i) { return (i - 1) / 2; }

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2 * i + 1); }

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2 * i + 2); }

    // Метод удаления минимального элемента (или корня) из минимальной кучи

    int extractMin()

    {

        if (heap_size <= 0)

            return Integer.MAX_VALUE;

        if (heap_size == 1) {

            heap_size--;

            return harr[0];

        }

        // Сохраняем минимальное значение и удаляем его из кучи

        int root = harr[0];

        harr[0] = harr[heap_size - 1];

        heap_size--;

        MinHeapify(0);

        return root;

    }

    // Вставляем новый ключ 'k'

    void insertKey(int k)

    {

        if (heap_size == capacity) {

            System.out.println("Overflow: Could not insertKey");

            return;

        }

        // Сначала вставляем новый ключ в конце

        heap_size++;

        int i = heap_size - 1;

        harr[i] = k;

        // Исправляем свойство min heap, если оно нарушено

        while (i != 0 && harr[parent(i)] > harr[i]) {

            swap(i, parent(i));

            i = parent(i);

        }

    }

    // Полезная функция для проверки

    // если размер кучи равен 1 или нет

    boolean isSizeOne()

    {

        return (heap_size == 1);

    }

    // Утилита для замены двух элементов

    void swap(int x, int y)

    {

        int temp = harr[x];

        harr[x] = harr[y];

        harr[y] = temp;

    }

    // Основная функция, которая возвращает

    // минимальная стоимость подключения n веревок

    // длины сохраняются в len [0..n-1]

    static int minCost(int len[], int n)

    {

        int cost = 0; // Инициализировать результат

        // Создание минимальной кучи емкости, равной

        // и положить все веревки в нем

        MinHeap minHeap = new MinHeap(len, n);

        // Итерация, пока размер кучи не становится 1

        while (!minHeap.isSizeOne()) {

            // Извлекаем две веревки минимальной длины из минимальной кучи

            int min = minHeap.extractMin();

            int sec_min = minHeap.extractMin();

            cost += (min + sec_min); // Обновить общую стоимость

            // Вставляем новую веревку в кучу мин с длиной, равной сумме

            // из двух извлеченных минимальных длин

            minHeap.insertKey(min + sec_min);

        }

        // Наконец возвращаем общий минимум

        // стоимость подключения всех канатов

        return cost;

    }

    // Код драйвера

    public static void main(String args[])

    {

        int len[] = { 4, 3, 2, 6 };

        int size = len.length;

        System.out.println("Total cost for connecting ropes is " + minCost(len, size));

    }

};

  
// Этот код предоставлен shubham96301

// C # программа для соединения n веревок с минимальными затратами

using System;

  
// Класс для Min Heap

class MinHeap 

{ 

    int[] harr; // Массив элементов в куче

    int heap_size; // Текущее количество элементов в мин куче

    int capacity; // максимально возможный размер кучи min

    // Конструктор: строит кучу из

    // заданный массив a [] заданного размера

    public MinHeap(int []a, int size) 

    { 

        heap_size = size; 

        capacity = size; 

        harr = a; 

        int i = (heap_size - 1) / 2; 

        while (i >= 0) 

        { 

            MinHeapify(i); 

            i--; 

        } 

    } 

    // Рекурсивный метод для подкачки поддерева

    // с корнем по заданному индексу

    // Этот метод предполагает, что поддеревья

    // уже куча

    void MinHeapify(int i) 

    { 

        int l = left(i); 

        int r = right(i); 

        int smallest = i; 

        if (l < heap_size && harr[l] < harr[i]) 

            smallest = l; 

        if (r < heap_size && harr[r] < harr[smallest]) 

            smallest = r; 

        if (smallest != i) 

        { 

            swap(i, smallest); 

            MinHeapify(smallest); 

        } 

    } 

    int parent(int i) { return (i - 1) / 2; } 

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2 * i + 1); } 

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2 * i + 2); } 

    // Метод удаления минимального элемента (или корня) из минимальной кучи

    int extractMin() 

    { 

        if (heap_size <= 0) 

            return int.MaxValue; 

        if (heap_size == 1) 

        { 

            heap_size--; 

            return harr[0]; 

        } 

        // Сохраняем минимальное значение и удаляем его из кучи

        int root = harr[0]; 

        harr[0] = harr[heap_size - 1]; 

        heap_size--; 

        MinHeapify(0); 

        return root; 

    } 

    // Вставляем новый ключ 'k'

    void insertKey(int k) 

    { 

        if (heap_size == capacity) 

        { 

            Console.WriteLine("Overflow: Could not insertKey"); 

            return; 

        } 

        // Сначала вставляем новый ключ в конце

        heap_size++; 

        int i = heap_size - 1; 

        harr[i] = k; 

        // Исправляем свойство min heap, если оно нарушено

        while (i != 0 && harr[parent(i)] > harr[i]) 

        { 

            swap(i, parent(i)); 

            i = parent(i); 

        } 

    } 

    // Полезная функция для проверки

    // если размер кучи равен 1 или нет

    Boolean isSizeOne() 

    { 

        return (heap_size == 1); 

    } 

    // Утилита для замены двух элементов

    void swap(int x, int y) 

    { 

        int temp = harr[x]; 

        harr[x] = harr[y]; 

        harr[y] = temp; 

    } 

    // Основная функция, которая возвращает

    // минимальная стоимость подключения n веревок

    // длины сохраняются в len [0..n-1]

    static int minCost(int []len, int n) 

    { 

        int cost = 0; // Инициализировать результат

        // Создание минимальной кучи емкости, равной

        // и положить все веревки в нем

        MinHeap minHeap = new MinHeap(len, n); 

        // Итерация, пока размер кучи не становится 1

        while (!minHeap.isSizeOne())

        { 

            // Извлекаем две веревки минимальной длины из минимальной кучи

            int min = minHeap.extractMin(); 

            int sec_min = minHeap.extractMin(); 

            cost += (min + sec_min); // Обновить общую стоимость

            // Вставляем новую веревку в кучу мин с длиной, равной сумме

            // из двух извлеченных минимальных длин

            minHeap.insertKey(min + sec_min); 

        } 

        // Наконец возвращаем общий минимум

        // стоимость подключения всех канатов

        return cost; 

    } 

    // Код драйвера

    public static void Main(String []args) 

    { 

        int []len = { 4, 3, 2, 6 }; 

        int size = len.Length; 

        Console.WriteLine("Total cost for connecting ropes is " + 

                                            minCost(len, size)); 

    } 

}; 

  
// Этот код предоставлен Арнабом Кунду

#include <iostream>
#include <queue>

using namespace std;

int minCost(int arr[], int n)

{

    // Создать приоритетную очередь ( http: // www.cplusplus.com/reference/queue/priority_queue/)

    // По умолчанию используется «меньше», что для убывания порядка

    // и «больше» используется для увеличения порядка

    priority_queue<int, vector<int>, greater<int> > pq(arr, arr + n);

    // Инициализировать результат

    int res = 0;

    // размер очереди с приоритетом больше 1

    while (pq.size() > 1) {

        // Извлекаем кратчайшие две веревки из pq

        int first = pq.top();

        pq.pop();

        int second = pq.top();

        pq.pop();

        // Соединяем веревки: обновляем результат и

        // вставляем новый трос в pq

        res += first + second;

        pq.push(first + second);

    }

    return res;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int len[] = { 4, 3, 2, 6 };

    int size = sizeof(len) / sizeof(len[0]);

    cout << "Total cost for connecting ropes is " << minCost(len, size);

    return 0;

}

// Java программа для подключения
// веревки с минимальной стоимостью

import java.util.*;

class ConnectRopes {

    static int minCost(int arr[], int n)

    {

        // Создать приоритетную очередь

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // Добавление элементов в pQueue

        for (int i = 0; i < n; i++) {

            pq.add(arr[i]);

        }

        // Инициализировать результат

        int res = 0;

        // Пока размер очереди приоритета

        // больше 1

        while (pq.size() > 1) {

            // Извлекаем кратчайшие две веревки из pq

            int first = pq.poll();

            int second = pq.poll();

            // Соединяем веревки: результат обновления

            // и вставляем новую веревку в pq

            res += first + second;

            pq.add(first + second);

        }

        return res;

    }

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        int len[] = { 4, 3, 2, 6 };

        int size = len.length;

        System.out.println("Total cost for connecting"

                           + " ropes is " + minCost(len, size));

    }

}
// Этот код предоставлен yash_pec