向下调整：时间复杂度 O (log n)

建大根堆：数学推导 -> O (N)

插入元素：向上调整

1. Java中优先级队列的使用

PriorityQueue<Integer> queue = new PriorityQueue<>();

2. TOP -K 问题

优先级队列 -> 用堆完成

1. 将前K个元素建成小堆
2. 从第K+1个元素开始，每次和堆顶去比较。（如果这个元素大于堆顶的元素，就把堆顶的元素出队列）调整元素的时间复杂度为O (N*lg(K))

public class test {
    //topK 函数
    public static int[] topK(int[] array, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < array.length; i++) {
            if(minHeap.size() < k) {
                minHeap.offer(array[i]);
            } else {
                int top = minHeap.peek();
                if (top < array[i]) {
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        //minHeap存储是就是前K个最大的元素
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }
    //程序主函数
    public static void main(String[] args) {
        int[] array = {10,8,100,78,126,30};
        int [] ret = topK(array,3);
        System.out.println(Arrays.toString(ret));
    }
}

3. 堆排序

从小到大排序：建大堆，从后往前

//排序
    public void heapSort() {
        int end = this.usedSize-1;
        while (end > 0) {
            int tmp = this.elem[0];
            this.elem[0] =this.elem[end];
            this.elem[end] = tmp;
            shiftDown2(0,end);
            end--;
        }
    }
    //向下排序调用
    public void shiftDown2(int parent, int len) {
        int child = 2*parent+1;
        //进入这个循环，说明最起码有左孩子
        while (child < len) {
            if(child+1 < len && this.elem[child] < this.elem[child+1]) {
                child++;
            }
            //child保存的下标，就是左右孩子的最大值
            if (this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }
    public void show() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
    }