Priority queue

Priority queue

The underlying data structure that priority queues rely on is typically the heap.

Classification: heap and small heap

If the root is bigger than the left and right children, it’s called a heap. The root is smaller than the left and right children, so it’s called a small heap, and the root of a large heap is the maximum, and the root of a small heap is the minimum. Adjusting the heap time to O(LGN) every time there is an element push or pop is also very fast.

said

Most of the time, arrays are used to represent a heap, not binary trees. This is because:

• The memory of the array is continuous and the access speed is faster.
• The heap structure is a complete binary tree.

The rules of heap are as follows:

• The parent of I is par = (i-1)/2
• The left child of I is 2 times I plus 1
• The right child of I is 2 times I plus 2

operation

sinking

    /** * sink 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;
    }
Copy the code

floating

    /** * float up 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;
    }
Copy the code

POP

    /**
     * pop
     *
     * @return* /
    private int pop(a){
        int ret =arr[0];
        arr[0] = arr[--n];
        sink(0);
        return ret;
    }
Copy the code

push

    /** * push */
    private void push(int v){
        arr[n++] = v;
        swim(n-1);
    }
Copy the code

Queue size

 /**
   * 队列大小
   */
 private int size(a) {
     return n;
 }
Copy the code

The smallest number of K

Given an array a[], return the smallest K number in the array

Input: A=[3,2,1], k=2

Output: [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;
    }
Copy the code

jumping

Title: Suppose you are playing a jumping game. There are two ways to jump from a low place to a high place. Method 1: Stuff blocks, but there is a limit to how many blocks you can have. For simplicity, the height difference is the number of bricks you need. Method 2: Use ladders. Ladders can ignore the height difference (you can assume you can climb even higher), but there are a limited number of ladders (one can only be used once). The rest of the jump can be done flat, or from a high place to a low place, without any help. You are given an array of different heights. Suppose you always start at index = 0. So, what’s the furthest you can jump?

Enter: [3, 1, 6, 20, 10, 20], bricks = 5, landers = 1

Output: 4

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

        // Take care to handle illegal input
        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;
    }
Copy the code

Number of refueling times

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;
    }
Copy the code