数据结构之优先级队列(堆)及top-k问题讲解（一）

// 根据传入的数组  将他们调整为大根堆
    public int[] elem;
    public int usedSize;
    public TestHeap(int size) {
        this.elem = new int[size];
    }
    // 初始化堆
    public void initHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            this.usedSize++;
        }
    }
    // 实现大根堆
    /**
     * 从最后一棵子树的根节点开始，进行向下调整，一直调整到root
     */
        // 向下调整
    public void createHeap() {
        // 从最后一棵子树的根节点开始
        for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) {
            shiftDown(parents,usedSize);
        }
    }
    private void shiftDown(int parents, int usedSize) {
        // 先获取左孩子的下标
        int child = 2*parents + 1;
        // 进行向下调整
        while (child < usedSize) {
            // 先判断左右孩子的值是谁更大
            if(child+1 < usedSize && elem[child] < elem[child+1]) {
                // 存在右孩子  且右孩子的值比左孩子的大
                child++;
            }
            if(elem[child] > elem[parents]) {
                // 如果孩子结点的值比根节点大  交换
                swap(child,parents);
                parents = child;
                child = 2*parents + 1;
            }else {
                // 如果根节点就是最大值  直接翻一下
                break;
            }
        }
    }
    // 交换函数
    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

// 实现小根堆
    public void createHeap2() {
        // 从最后一棵子树的根节点开始
        for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) {
            shiftDown(parents,usedSize);
        }
    }
    private void shiftDown2(int parents, int usedSize) {
        // 先获取左孩子的下标
        int child = 2*parents + 1;
        // 进行向下调整
        while (child < usedSize) {
            // 先判断左右孩子的值是谁更大
            if(child+1 < usedSize && elem[child] > elem[child+1]) {
                // 存在右孩子  且右孩子的值比左孩子的小
                child++;
            }
            if(elem[child] < elem[parents]) {
                // 如果孩子结点的值比根节点小  交换
                swap(child,parents);
                // parent中大的元素向下移动  可能会造成子树不满足堆的性质  继续进行向下调整
                parents = child;
                child = 2*parents + 1;
            }else {
                // 如果根节点就是最大值  
                break;
            }
        }
    }

// 堆的创建
    public void createHeap() {
        // 从最后一棵子树的根节点开始
        for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) {
            shiftDown(parents,usedSize);
        }
    }

// 在堆内添加元素
    /**
     * 插入到最后一个位置（保证是一个完全二叉树，且方便后续操作）
     * 向上调整
     */
    public void offer(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[usedSize] = val;
        shiftUp(usedSize);
        this.usedSize++;
    }
    private void shiftUp(int child) {
        int parent = (child-1)/2;
        // == 0此时就是根节点了  不需要再去向上调整
        // 需要一直调整到根节点
        while(child != 0) {
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    private boolean isFull() {
        return this.usedSize == this.elem.length;
    }

// 删除  一定是删除优先级最高的元素  最后返回优先级最高的那个元素
    public int poll() {
        // 优先级最高的元素就是顺序表elem 的首元素
        int tmp = elem[0];
        swap(0,usedSize-1);
        this.usedSize--;
        // 只需对堆顶元素进行向下调整
        shiftDown(0,usedSize);
        return tmp;
    }

PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student());
        priorityQueue2.offer(new Student());// 报错

PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);
        priorityQueue1.offer(4);
        priorityQueue1.offer(5);
        System.out.println(priorityQueue1.poll());// 输出1