题解 | #缺失数字#

Java 自建小顶堆实现

import java.util.PriorityQueue;
import java.io.*;
public class Main {
    static final StreamTokenizer st = 
        new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }
    
    public static void main(String[] sss) {
        int n = nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }
        
        long ans = minSplitCost(arr);
        System.out.println(ans);
    }
    
//     private static long minSplitCost(int[] arr) {
//         if (arr == null || arr.length < 2) {
//             return 0;
//         }
        
//         /*
//             哈夫曼编码应用：贪心
//         */

//         int n = arr.length;
//         // 优先队列就是小根堆
//         PriorityQueue<Long> minHeap = new PriorityQueue<>();
//         for (int i = 0; i < n; i++) {
//             minHeap.add((long) arr[i]);
//         }
        
//         long res = 0;
//         long sum;
//         while (minHeap.size() != 1) {
//             sum = minHeap.poll() + minHeap.poll();
//             res += sum;
//             minHeap.add(sum);
//         }
        
//         return res;
//     }
    
    private static long minSplitCost(long[] arr) {
        if (arr == null || arr.length < 2) return 0;
        /*
            哈夫曼编码的应用：贪心
            每次选两个最小的数，相加后的和再重新入堆，直到剩一个数
         */

        int n = arr.length;
        // 建堆
        for (int i = 1; i < n; i++) {
            heapInsert(arr, i);
        }

        int sz = n;
        long res = 0;
        long sum;
        while (sz != 1) {
            swap(arr, 0, sz - 1);
            heapify(arr, 0, sz - 1);
            swap(arr, 0, sz - 2);
            heapify(arr, 0, sz - 2);

            sum = arr[sz - 1] + arr[sz - 2];
            res += sum;

            arr[sz - 2] = sum;
            heapInsert(arr, sz - 2);
            sz--;
        }

        return res;
    }

    private static void heapify(long[] minHeap, int p, int sz) {
        int lch = 2 * p + 1;
        int rch = 2 * p + 2;
        int minIdx = p;
        while (lch < sz) {
            if (minHeap[lch] < minHeap[minIdx]) {
                minIdx = lch;
            }

            if (rch < sz && minHeap[rch] < minHeap[minIdx]) {
                minIdx = rch;
            }

            if (minIdx == p) break;

            swap(minHeap, p, minIdx);
            p = minIdx;
            lch = 2 * p + 1;
            rch = 2 * p + 2;
        }
    }

    private static void heapInsert(long[] minHeap, int k) {
        int p;
        while (k > 0) {
            p = (k - 1) / 2;
            if (minHeap[p] > minHeap[k]) {
                swap(minHeap, p, k);
                k = p;
            } else {
                break;
            }
        }
    }

    private static void swap(long[] arr, int i, int j) {
        long t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}