优先队列

我们想实现的是什么？
优先队列的堆实现 需要实现的功能有两个

1. 增加结点
   增加的结点需要满足上层结点大于下层结点，如果新增的结点不在合适位置（也就是当前位置的上层结点有比新增结点小的值），然后需要把这个结点上浮（如果比上层结点大，和对应的上层结点交换，循环到根节点）
2. 删除根节点（最大值）
   删除根节点之后需要重新选一个最大值，把最后一个结点的值赋值给根结点（也就是pq[1]）pq[0]不存值。然后，pq[1]下沉到合适位置。

上浮和下沉

1. swim
2. sink

和二叉查找树的区别：

堆 父结点需要大于两个子结点 用链表存
二叉查找树 左子结点小于父节点， 右子结点大于父结点 用数组存

结点

基于堆优先队列结点的结构（后面简称堆），堆是完全二叉树并且是平衡的
根节点最大 ，同层结点可以不按大小排序，但是上层的节点比下层节点大。

增加节点

删除节点

因为实现的是优先队列，删除

public class PQ<Key extends Comparable<Key>>{
    private Key[] pq;
    private int N = 0;
    
    @SuppressWarnings("unchecked")
    public PQ(int maxN){
        pq = (Key[])new Comparable[maxN + 1];
    }
    public boolean isEmpty(){
        return N == 0;
    }
    public int size(){
        return N;
    }
    public void insert(Key v){
        pq[++N] = v;
        swim(N);
    }
    public Key delMax(){
        Key max = pq[1];
        exch(1, N--);
        pq[N + 1] = null;
        sink(1);
        return max;
    }
    private void sink(int k) {
        //删除最大结点是下沉     
//**这个操作之前会把最后一个元素赋值给第一个元素  然后让这个元素下沉到合适位置  而不是直接和第一个最大值比较 （因为这个值是被删掉的值）**
        while(2*k <= N){
            int j = 2*k;
            if(j < N && less(j, j+1)){
                j++;
            }
            if(!less(k, j)){
                //出现后面的值没有a[k]大的时候就表示到了合适位置， 因为下面的值都是较小的值   （有序）
                break;
            }
            exch(k, j);
            k = j;
        }
    }
    private boolean less(int j, int i) {
        
        return pq[j].compareTo(pq[i]) < 0 ? true : false;
    }
    private void exch(int i, int j) {
        Key tmp = pq[j];
        pq[j] = pq[i];
        pq[i] = tmp;
    }
    private void swim(int k) {
        while(k > 1 && less(k/2, k)){
            exch(k/2, k);
            k = k/2;
        }
    }
}

@Test
    public void test(){
        int maxN = 10;
        PQ<Integer> p = new PQ<>(maxN);
        p.insert(1);
        p.insert(2);
        p.insert(3);
        p.insert(4);
        p.insert(5);
        p.insert(6);
        p.delMax();
        p.delMax();
        p.delMax();
        System.out.println();
    }