//parent: 每棵樹的根節(jié)點(diǎn)
 //len: 每棵樹的調(diào)整的結(jié)束位置
public void shiftDown(int parent,int len){
        int child=parent*2+1; //因?yàn)槎咽峭耆鏄?，沒有左孩子就一定沒有右孩子，所以最起碼是有左孩子的，至少有1個(gè)孩子
        while(child<len){
            if(child+1<len && elem[child]<elem[child+1]){
                child++;//兩孩子結(jié)點(diǎn)比較取較小值
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

public void creatHeap(int[] arr){
        for(int i=0;i<arr.length;i++){
            elem[i]=arr[i];
            useSize++;
        }
        for(int parent=(useSize-1-1)/2;parent>=0;parent--){//數(shù)組下標(biāo)從0開始
            shiftDown(parent,useSize);
        }
    }

public void shiftup(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

public boolean isFull(){
        return elem.length==useSize;
    }
public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);//擴(kuò)容
        }
        elem[useSize++]=val;
        shiftup(useSize-1);
    }

public boolean isEmpty(){
        return useSize==0;
    }
public int poll(){
        if(isEmpty()){
            throw new RuntimeException("優(yōu)先級(jí)隊(duì)列為空");
        }
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDown(0,useSize);
        return tmp;
    }

public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("優(yōu)先級(jí)隊(duì)列為空");
        }
        return elem[0];
    }

 public static int[] topK(int[] array,int k){
        //創(chuàng)建一個(gè)大小為K的小根堆
        PriorityQueue<Integer> minHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        //遍歷數(shù)組中元素，將前k個(gè)元素放入隊(duì)列中
        for(int i=0;i<array.length;i++){
            if(minHeap.size()<k){
                minHeap.offer(array[i]);
            }else{
                //從k+1個(gè)元素開始，分別和堆頂元素比較
                int top=minHeap.peek();
                if(array[i]>top){
                    //先彈出后存入
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        //將堆中元素放入數(shù)組中
        int[] tmp=new int[k];
        for(int i=0;i< tmp.length;i++){
            int top=minHeap.poll();
            tmp[i]=top;
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] array={12,8,23,6,35,22};
        int[] tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);//假設(shè)這里向下調(diào)整為大根堆
            end--;
        }
    }