优先级队列

优先级队列

优先级队列底层依赖的数据结构一般是堆。

分类: 大堆和小堆

根比左右子结点都大，那么称为大堆.根比左右子结点都要小，那么称为小堆，大堆的根是最大值，小堆的根是最小值。每次有元素 push 或者 pop 的时候，调整堆的时间复杂度为 O(lgn)，速度也非常快。

表示

大部分时候都是使用数组表示一个堆，而不是使用二叉树。这是因为:

• 数组的内存具有连续性，访问速度更快；
• 堆结构是一棵完全二叉树。

堆的规律有如下几点：

• i 结点的父结点 par = (i-1)/2
• i 结点的左子结点 2 * i + 1
• i 结点的右子结点 2 * i + 2

操作

下沉

    /**
     * 下沉  O(lgN)
     */
    private void sink(int i) {
        int j = 0;
        int t = arr[i];
        while ((j = (i << 1) + 1) < n) {
            if (j < n - 1 && arr[j] < arr[j + 1]) {
                j++;
            }

            if (arr[j] > t) {
                arr[i] = arr[j];
                i = j;
            } else {
                break;
            }
        }
        arr[i] = t;
    }
复制代码

上浮

    /**
     * 上浮 O(lgN)
     */
    private void swim(int i) {
        int j = 0;
        int t = arr[i];
        while (i > 0) {
            j = (i - 1) >> 1;
            if (arr[j] < t) {
                arr[i] = arr[j];
                i = j;
            } else {
                break;
            }
        }
        arr[i] = t;
    }
复制代码

POP

    /**
     * pop
     *
     * @return
     */
    private int pop(){
        int ret =arr[0];
        arr[0] = arr[--n];
        sink(0);
        return ret;
    }
复制代码

push

    /**
     * push
     */
    private void push(int v){
        arr[n++] = v;
        swim(n-1);
    }
复制代码

队列大小

 /**
   * 队列大小
   */
 private int size() {
     return n;
 }
复制代码

最小的K个数

题目: 给定一个数组a[], 返回这个数组中最小的K个数

输入: A=[3,2,1], k=2

输出: [2,1]

    private int[] getLeastNumbers(int[] a, int k) {
        if (k < 0 || a == null || a.length == 0) {
            return new int[0];
        }

        arr = new int[a.length];
        n = 0;
        for (int x : a) {
            push(x);
            if (size() > k) {
                pop();
            }
        }

        int[] resultArr = new int[k];
        int i = 0;
        while (size() > 0) {
            resultArr[i++] = pop();
        }
        return resultArr;
    }
复制代码

跳跃

题目: 假设你正在玩跳跃游戏，从低处往高处跳的时候，可以有两种方法。方法一：塞砖块，但是你拥有砖块数是有限制的。为了简单起见，高度差就是你需要砖块数。方法二：用梯子，梯子可以无视高度差（你可以认为再高也能爬上去），但是梯子的个数是有限的(一个只能用一次)。其他无论是平着跳，还是从高处往低处跳，不需要借助什么就可以完成（在这道题中我们默认无论从多高跳下来，也摔不死）。给你一个数组，用来表示不同的高度。假设你总是站在 index = 0 的高度开始。那么请问，你最远能跳到哪里?

输入：[3, 1, 6, 20, 10, 20], bricks = 5, landers = 1

输出：4

private int furthestBuilding(int[] heights, int bricks, int ladders) {

        // 注意处理非法输入
        if (heights == null || heights.length == 0) {
            return -1;
        }

        Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
        int sum =0;
        int lastPos =0;
        int preHeight = heights[0];

        for (int i=1; i< heights.length; i++){
            final int curHeight = heights[i];
            if(preHeight >= curHeight){
                lastPos = i;
            } else {
                final int delta = curHeight - preHeight;
                queue.offer(delta);
                sum += delta;
                while(sum > bricks && ladders > 0){
                    sum -= queue.peek();
                    queue.poll();
                    ladders--;
                }
                if(sum <= bricks){
                    lastPos =i;
                }else {
                    break;
                }
            }
            preHeight = curHeight;
        }
        return lastPos;
    }
复制代码

汽车加油次数

private int minRefuelStops(int target, int startFuel, int[][] stations) {
        int i = 0;
        int curPos = 0;
        int fuelLeft = startFuel;
        Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
        int addFuelTimes = 0;
        while (curPos + fuelLeft < target) {
            int pos = target;
            int fuel =0;

            if(i< stations.length && stations[i][0] <= target){
                pos = stations[i][0];
                fuel = stations[i][1];
            }

            while(curPos +fuelLeft < pos){
                if(queue.isEmpty()){
                    return -1;
                }

                final int curMaxFuel = queue.peek();
                queue.poll();
                fuelLeft +=curMaxFuel;
                addFuelTimes ++;
            }

            final int fuelCost = pos - curPos;
            fuelLeft -= fuelCost;
            curPos = pos;

            if(fuel > 0){
                queue.offer(fuel);
            }
            i++;
        }
        return curPos + fuelLeft > target? addFuelTimes: -1;
    }
复制代码