# 1167.Minimum-Cost-to-Connect-Sticks

## 1167. Minimum Cost to Connect Sticks

## 题目地址

<https://leetcode.com/problems/minimum-cost-to-connect-sticks/>

## 题目描述

```
You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y.  You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3]
Output: 14
Example 2:

Input: sticks = [1,8,3,5]
Output: 30
```

## 代码

Approach 1: Heap

```java
class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = PriorityQueue<Integer>();

    for (int i = 0; i < n; i++) {
      pq.add(arr[i]);
    }

    int res = 0;

    while (pq.size() > 1) {
      int first = pq.poll();
      int second = pq.poll();

      res += first + second;
      pq.add(first + second);
    }

    return res;
    }
}
```

```java
class MinHeap { 
    int[] harr; // Array of elements in heap 
    int heap_size; // Current number of elements in min heap 
    int capacity; // maximum possible size of min heap 

    // Constructor: Builds a heap from 
    // a given array a[] of given size 
    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--; 
        } 
    } 

    // A recursive method to heapify a subtree 
    // with the root at given index 
    // This method assumes that the subtrees 
    // are already heapified 
    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; } 

    // to get index of left child of node at index i 
    int left(int i) { return (2 * i + 1); } 

    // to get index of right child of node at index i 
    int right(int i) { return (2 * i + 2); } 

    // Method to remove minimum element (or root) from min heap 
    int extractMin() 
    { 
        if (heap_size <= 0) 
            return Integer.MAX_VALUE; 
        if (heap_size == 1) { 
            heap_size--; 
            return harr[0]; 
        } 

        // Store the minimum value, and remove it from heap 
        int root = harr[0]; 
        harr[0] = harr[heap_size - 1]; 
        heap_size--; 
        MinHeapify(0); 

        return root; 
    } 

    // Inserts a new key 'k' 
    void insertKey(int k) 
    { 
        if (heap_size == capacity) { 
            System.out.println("Overflow: Could not insertKey"); 
            return; 
        } 

        // First insert the new key at the end 
        heap_size++; 
        int i = heap_size - 1; 
        harr[i] = k; 

        // Fix the min heap property if it is violated 
        while (i != 0 && harr[parent(i)] > harr[i]) { 
            swap(i, parent(i)); 
            i = parent(i); 
        } 
    } 

    // A utility function to check 
    // if size of heap is 1 or not 
    boolean isSizeOne() 
    { 
        return (heap_size == 1); 
    } 

    // A utility function to swap two elements 
    void swap(int x, int y) 
    { 
        int temp = harr[x]; 
        harr[x] = harr[y]; 
        harr[y] = temp; 
    } 

    // The main function that returns the 
    // minimum cost to connect n ropes of 
    // lengths stored in len[0..n-1] 
    static int minCost(int len[], int n) 
    { 
        int cost = 0; // Initialize result 

        // Create a min heap of capacity equal 
        // to n and put all ropes in it 
        MinHeap minHeap = new MinHeap(len, n); 

        // Iterate while size of heap doesn't become 1 
        while (!minHeap.isSizeOne()) { 
            // Extract two minimum length ropes from min heap 
            int min = minHeap.extractMin(); 
            int sec_min = minHeap.extractMin(); 

            cost += (min + sec_min); // Update total cost 

            // Insert a new rope in min heap with length equal to sum 
            // of two extracted minimum lengths 
            minHeap.insertKey(min + sec_min); 
        } 

        // Finally return total minimum 
        // cost for connecting all ropes 
        return cost; 
    } 
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/data-structure/1167.minimum-cost-to-connect-sticks.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.