优先级队列(堆)

public class TestHeap {
    public int[] elem;
    public int usedSize;
 
    public TestHeap() {
        this.elem = new int[10];
    }
 
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
 
    /**
     * 时间复杂度：O(N) 
     */
    //堆的创建
    public void createHeap() {
        for(int parent = (usedSize-1-1)/2;parent >= 0; parent--) {//从长度-1开始，第一个父亲结点为{（长度-1）-1}/2
            shiftDown(parent,usedSize);
        }
    }
 
    /**
     * 父亲下标
     * 每棵树的结束下标
     * @param parent
     * @param len
     */
    //向下调整—— 时间复杂度：logN
    public void shiftDown(int parent,int len) {
        int child = 2*parent + 1;//定义孩子节点
        //最起码 要有左孩子
        while(child < len) {//一共usedSize个数，孩子节点小于总长度
            //一定是有右孩子的情况下
            if(child+1 < len && elem[child] < elem[child+1]) {//child+1 < len防止越界
                child++;//右孩子节点大的话，child++就不变成了右孩子
            }
            //此时，child下标一定是左右孩子最大值的下标
            if(elem[child] > elem[parent]) {
                //当孩子节点大于父亲节点，使用第三方将最大和最小值交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //此时完成了交换，但是有一个问题完成交换之后的孩子节点与孩子的孩子节点此时的大小顺序又被打乱
                //所以让父亲节点等于孩子节点，孩子节点等于孩子的孩子节点继续比较大小
                parent = child;
                child = 2*parent + 1;
            }else {
                break;
            }
        }
    }
}

    //堆的插入：堆的插入使用向上调整
    public void offer(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;最大元素下标为插入元素，元素个数+1————11
        //向上调整
        shiftUp(usedSize-1);//10————下标为10
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //向上调整
    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //继续向上调整，孩子节点为原来的父亲节点，父亲的父亲的节点为父亲节点
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    //堆的删除——删除的一定是堆顶元素
    //第一步：让堆顶元素和堆中最后一个元素交换    第二步：这时候有效数据减少一个，这时候只需要调整0下标这棵树     第三步： 使用向下调整
    public void pop() {
        if(isEmpty()) {
            return;
        }
        swap(elem,0,usedSize-1);
        usedSize--;//交换堆顶元素和堆中最后一个元素，此时数据减少一个
        shiftDown(0,usedSize);//向下调整
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
    //交换
    public void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //向下调整 时间复杂度——logN
    private void shiftDown(int parent,int len) {
        int child = 2*parent + 1;//定义孩子节点
        //最起码 要有左孩子
        while (child < len) {//一共usedSize个数，孩子节点小于总长度
            //一定是有右孩子的情况下
            if(child+1 < len && elem[child] < elem[child+1]) {//child+1 < len防止越界
                child++;//右孩子节点大的话，child++就不变成了右孩子
            }
            //child下标 一定是左右孩子 最大值的下标
            if(elem[child] > elem[parent]) {
                //当孩子节点大于父亲节点，使用第三方将最大和最小值交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //此时完成了交换，但是有一个问题完成交换之后的孩子节点与孩子的孩子节点此时的大小顺序又被打乱
                //所以让父亲节点等于孩子节点，孩子节点等于孩子的孩子节点继续比较大小
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

importjava.util.PriorityQueue;

//创建一个空的优先级队列，默认容量是11且默认没有比较器
PriorityQueue()     
 
 
//创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常        
PriorityQueue(int initialCapacity)
 
 
//用一个集合来创建优先级队列
PriorityQueue(Collection<?extends E> c)          

    //最小K个数
    //设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
        //O(N*logN)————向上调整
        Queue<Integer> minHeap = new PriorityQueue<>(arr.length);
        for (int x:arr) {
            minHeap.offer(x);//遍历小根堆，放入小根堆中
        }
        //O(k*logN)————弹k次，每次向下调整
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    /**
     * 前K个最大的元素   时间复杂度：N*logK
     * @param arr
     * @param k
     * @return
     */
    public int[] maxK2(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
 
        Queue<Integer> minHeap = new PriorityQueue<>(k);//建立大小为k的小根堆
 
        //1.遍历数组的前K个  放到堆当中
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);//前K个小根堆
        }
        //2.遍历剩下的数据，每次和堆顶元素进行比较
        //堆顶元素  小的时候，就出堆
        for (int i = k; i < arr.length; i++) {
            int val = minHeap.peek();//查看堆顶元素
            if(val < arr[i]) {//数组的元素大于堆顶元素
                minHeap.poll();//弹入堆当中,放入即为最后一个位置
                minHeap.offer(arr[i]);
            }
        }
        //放入数组中
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }