我们想实现的是什么？
优先队列的堆实现 需要实现的功能有两个
- 增加结点
增加的结点需要满足上层结点大于下层结点，如果新增的结点不在合适位置（也就是当前位置的上层结点有比新增结点小的值），然后需要把这个结点上浮（如果比上层结点大，和对应的上层结点交换，循环到根节点） - 删除根节点（最大值）
删除根节点之后需要重新选一个最大值，把最后一个结点的值赋值给根结点（也就是pq[1]）pq[0]不存值。然后，pq[1]下沉到合适位置。
上浮和下沉
- swim
- 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();
}
