堆算法

堆总是满足下列性质：
    1、堆中某个节点的值总是不大于或不小于其父节点的值；
    2、堆总是一棵完全二叉树。
应用：堆排序可以实现时间复杂度为nlogn
堆的基本操作
    上浮 shift_up；
    下沉 shift_down
    插入 push
    弹出 pop
    取顶 top
    堆排序 heap_sort

应用实例
PriorityQueue：优先队列，具备了小根堆的性质

public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    // 构建二维数数组并按照效率降序排序
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; i++) {
        arr[i][0] = speed[i];
        arr[i][1] = efficiency[i];
    }
    // 按效率降排序
    Arrays.sort(arr, (a, b) -> b[1] - a[1]);
    // 小根堆
    PriorityQueue<Integer> priorityQueue = new PriorityQueue();
    long sum = 0;
    long res = 0;
    // 计算效率
    for (int i = 0; i < n; i++) {
        priorityQueue.add(arr[i][0]);
        sum += arr[i][0];
        // 当堆中的数据超过k时，将最小的移除
        if (priorityQueue.size() > k) {
            sum -= priorityQueue.poll();
        }
        res = Math.max(res, sum * arr[i][1]);
    }
    System.out.println("res:" + res);
    return (int)(res % ((int)1e9 + 7));
}