原地堆化

原地堆化复杂度为 $\mathcal{O}(n)$ ；

class Solution {
    public long pickGifts(int[] gifts, int k) {
        int[] heap = new int[gifts.length + 1];
        System.arraycopy(gifts, 0, heap, 1, gifts.length);
        
        buildHeap(heap);

        for (int i = 0; i < k; i++) {
            heap[1] = (int)Math.sqrt(heap[1]);
            adjustDown(heap, 1);
        }

        long result = 0;
        for (int it : heap) result += it;

        return result;
    }

    private void buildHeap(int[] heap) {
        for (int i = heap.length >> 1; i > 0; i--) adjustDown(heap, i);
    }

    private void adjustDown(int[] heap, int idx) {
        for (int next = idx << 1; next < heap.length; next <<= 1) {
            if (next + 1 < heap.length && heap[next | 1] > heap[next]) next |= 1;
            if (heap[next] <= heap[idx]) break;
            int tmp = heap[idx];
            heap[idx] = heap[next];
            heap[next] = tmp;
            idx = next;
        }
    }
}

经典版 - 支持索引

只能取最小，支持 int， list[0] 为结尾下标。

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    static void heapOffer(int[] list, int[] item,  int val) {
        list[++list[0]] = val;
        heapUp(list, item, list[0]);
    }
    static void heapUp(int[] list, int[] item, int cIndex) {
        int pIndex = cIndex >> 1;
        while (cIndex > 1 && item[list[cIndex]] < item[list[pIndex]]) {
            swap(list, cIndex, pIndex);
            cIndex >>= 1;
            pIndex = cIndex >> 1;
        }
    }
    static int heapPoll(int[] list, int[] item) {
        final int res = list[1];
        swap(list, 1, list[0]--);
        heapDown(list, item, 1);
        return res;
    }
    static void heapDown(int[] list, int[] item, int cIndex) {
        final int end = list[0];
        int lIndex, rIndex, tIndex;
        while (cIndex < end) {
            lIndex = cIndex << 1;
            rIndex = cIndex << 1 | 1;
            if (lIndex > end) break;
            if (rIndex > end || item[list[lIndex]] < item[list[rIndex]]) tIndex = lIndex;
            else tIndex = rIndex;
            if (item[list[cIndex]] > item[list[tIndex]]) {
                swap(list, cIndex, tIndex);
                cIndex = tIndex;
            } else break;
        }
    }

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