二叉堆

父结点索引 i/2

左孩子结点索引 2*i 右孩子结点索引2*i

最大堆：每个结点都大于等于它的两个左右子结点

优先级队列

功能：插入和删除元素，元素会自动排序。底层二叉树操作

最大优先级队列代码实现：

public class MaxPQ <Key extends Comparable<Key>> { // Key是任何一种可比较大小的数据类型
    // 存储元素的数组
    private Key[] pq;
    // 当前 Priority Queue 中的元素个数
    private int size = 0;

    public MaxPQ(int cap) {
        // 索引 0 不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    /* 返回当前队列中最大元素 */
    public Key max() {
        return pq[1];
    }

    /* 插入元素 e */
    public void insert(Key e) {
        //先插入到堆底，然后上浮
        size++;
        pq[size]=e;
        swim(size);
    }

    /* 删除并返回当前队列中最大元素 */
    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max=pq[1];
        // 把最大元素放到最后，并删除
        swap(1,size);
        pq[size]=null;
        size--;
        // 调整堆
        sink(1);
        return max;
    }

    /* 上浮第 x 个元素，以维护最大堆性质 */
    private void swim(int x) {
        while(x>1 && less(parent(x),x)){ //当前结点比父结点大
            swap(parent(x),x);
            x=parent(x);
        }
    }

    /* 下沉第 x 个元素，以维护最大堆性质 */
    // 下沉某个结点，需要该结点和其左右子节点比较，如果该结点不是最大的，就和较大的子节点交换
    private void sink(int x) {
        // 直到到堆底
        while(left(x) <=size){
            int max=left(x); //记录左右子节点较大的那个
            if(right(x)>=size && less(max,right(x))){ // 右结点一定要存在
                max=right(x);
            }
            if(less(max,x)){  //当前结点比左右结点大，不必下沉
                break;
            }
            swap(max,x);
            x=max;
        }
    }

    /* 交换数组的两个元素 */
    private void swap(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /* pq[i] 是否比 pq[j] 小？ */
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    /* 父结点索引 */
    private int parent(int i){
        return i/2;
    }
    /* 左孩子结点索引 */
    private int left(int i){
        return i*2;
    }
    /* 右孩子结点索引 */
    private int right(int i){
        return i*2+1;
    }
}

Java优先级队列实现类 PriorityQueue

二叉堆与平衡二叉树比较

优先级队列实现的二叉堆只能取最值(删除最值)，时间复杂度为O(logn),无法对二叉堆的一些值进行修改

平衡二叉树也可以取最值，也可以修改、删除任意一个值，而且时间复杂度都是 O(logN)。 –> java中的TreeSet

常数时间删除/查找数组中的任意元素

力扣第 380 题「常数时间插入、删除和获取随机元素」

本题的难点在于两点：

**1、插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)**。

2、getRandom 方法返回的元素必须等概率返回随机元素，也就是说，如果集合里面有 n 个元素，每个元素被返回的概率必须是 1/n

HashSet可以实现O(1)内插入，删除，但无法等概率返回随机元素

对于 getRandom 方法，如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。

用数组（List），插入删除操作O(1),就不能移动元素，使用HashMap记录元素与索引之间的关系。

最麻烦的应该是删除操作：更新map,最后一个元素直接删除，不是最后一个，和最后一个元素交换

疑问：remove()方法有根据索引的，有根据值的，下面是根据索引还是值？

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(0);
    list.remove(0);
    System.out.println(list); 【1，2】
}

它是根据索引删除的，并没有根据值

力扣第 710 题「黑名单中的随机数」

随机生成一个[0,sz), 如果生成的数在黑名单上，映射到sz后面的数

单调栈

单调栈用于解决一类题，解决下一类更大元素的问题

eg:一个数组 nums = [2,1,2,4,3]，返回结果 [4,2,4,-1,-1]。

暴力解法：O(n^2) 单调栈：O(n)

算法模板

int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.isEmpty() && s.peek() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的更大元素
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}