//建堆前
int array[]={1,5,3,8,7,6};
//建堆后
int array[]={ 8,7,6,5,1,3 };

 public static void shiftDown(int[] array,int parent){
        int child=2*parent+1;
        while (child<array.length){
            if(child+1<array.length){
                if (array[child]<array[child+1]){
                    child++;
                }
            }
            if(array[child]>array[parent]){
                int tmp=array[child];
                array[child]=array[parent];
                array[parent]=tmp;
                parent=child;
                child=parent*2+1;
            }
            else {
                break;
            }
        }
    }
    public static void createHeap(int[] array){
        for (int i = (array.length-1-1)/2; i >=0; i--) {
            shiftDown(array,i);
        }
    }
    public static void main(String[] args) {
        int array[]={1,5,3,8,7,6};
        createHeap(array);
        System.out.println(Arrays.toString(array));
    }

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];//先創(chuàng)建長度為10的數(shù)組
    }
    public  boolean isFull() {
        return this.usedSize == this.elem.length;
    }
    public void push(int val) {
    //先判斷隊(duì)列是否已經(jīng)滿，如果以滿則擴(kuò)容
        if (isFull()){
            Arrays.copyOf(this.elem,this.elem.length*2);
        }
        this.elem[this.usedSize++]=val;
        shiftUp(this.usedSize-1);
    }
    public void shiftUp(int child) {
        int parent=(child-1)/2;
        while (parent>=0){
            if(this.elem[child]>this.elem[parent]){
                int tmp=this.elem[child];
                this.elem[child]=this.elem[parent];
                this.elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }
            else{
                break;
            }
        }
    }
    
}

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];//10個(gè)0
    }
    public  boolean isFull() {
        return this.usedSize == this.elem.length;
    }
    public  boolean isEmpty() {
        return this.usedSize == 0;
    }
    public int poll() {
        //先判斷隊(duì)列是否為空，如果為空則拋出異常
        if (isEmpty()){
            throw new RuntimeException("優(yōu)先級隊(duì)列為空");
        }
        int tmp=this.elem[0];
        this.elem[0]=this.elem[this.usedSize-1];
        this.usedSize--;
        shiftDown(0);
        return tmp;
    }
    public void shiftDown(int parent) {
        int child = 2*parent+1;
        //進(jìn)入這個(gè)循環(huán) 說明最起碼你有左孩子
        while (child < this.usedSize) {
        	//該條件進(jìn)入是判斷其是否有右兄弟
            if(child+1 < this.usedSize &&
             this.elem[child] < this.elem[child+1]) {
                child++;
            }
            //child所保存的下標(biāo)，就是左右孩子的最大值
            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;//如果孩子節(jié)點(diǎn)比父親節(jié)點(diǎn)小 直接結(jié)束了
            }
        }
    }
}

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

PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator(Integer)){
public int compare(Integer o1,Integer o2){return o2-o1}
};

class Solution {
 public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);//改為大堆
        for(int i=0;i<stones.length;i++){
            queue.offer(stones[i]);
        }
            while(queue.size()>=2){
            int max1=queue.poll();
            int max2=queue.poll();
            int sum=max1-max2;
            if(sum>0){
                queue.offer(sum);
            }
        }
        if(queue.size()>0){
            return queue.poll();
        }
        return 0;
    }
}

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
    PriorityQueue<Integer> queue=new PriorityQueue<>();
        List<Integer> list=new ArrayList<>();
        if(k>arr.length){
            for (int num:arr) {
                list.add(num);
            }
        }
        else {
            for (int i = 0; i < arr.length; i++) {
                if(i<k){
                    queue.offer(arr[i]);
                }
                else {
                    int sum1=Math.abs(arr[i]-x);
                    int sum2=Math.abs(queue.peek()-x);
                    if(sum1<sum2){
                        queue.poll();
                        queue.offer(arr[i]);
                    }
                }
            }
            while (!queue.isEmpty()){
                list.add(queue.poll());
            }
        }
        return list;
    }
}

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue=new PriorityQueue<>(k,(o1,o2)->{
            return o2.get(0)+o2.get(1)-o1.get(0)-o1.get(1);
        });
        for (int i=0;i<Math.min(nums1.length,k);i++)
        {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                List<Integer> list=new ArrayList<>();
                if (queue.size()<k){
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    queue.offer(list);
                }
                else {
                    int tmp=queue.peek().get(0)+queue.peek().get(1);
                    if(nums1[i]+nums2[j]<tmp){
                        queue.poll();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        queue.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> list=new ArrayList<>();
        for (int i = 0; i < k&&!queue.isEmpty(); i++) {
            list.add(queue.poll());
        }
        return list;
    }
}