我們想實現(xiàn)的是什么？
優(yōu)先隊列的堆實現(xiàn) 需要實現(xiàn)的功能有兩個
- 增加結(jié)點
增加的結(jié)點需要滿足上層結(jié)點大于下層結(jié)點胸墙，如果新增的結(jié)點不在合適位置（也就是當(dāng)前位置的上層結(jié)點有比新增結(jié)點小的值），然后需要把這個結(jié)點上付稀（如果比上層結(jié)點大树叽，和對應(yīng)的上層結(jié)點交換，循環(huán)到根節(jié)點） - 刪除根節(jié)點（最大值）
刪除根節(jié)點之后需要重新選一個最大值诊霹，把最后一個結(jié)點的值賦值給根結(jié)點（也就是pq[1]）pq[0]不存值。然后渣淳，pq[1]下沉到合適位置脾还。
上浮和下沉
- swim
- sink
和二叉查找樹的區(qū)別：
堆 父結(jié)點需要大于兩個子結(jié)點 用鏈表存
二叉查找樹 左子結(jié)點小于父節(jié)點， 右子結(jié)點大于父結(jié)點 用數(shù)組存
結(jié)點
基于堆優(yōu)先隊列結(jié)點的結(jié)構(gòu)（后面簡稱堆）入愧，堆是完全二叉樹并且是平衡的
根節(jié)點最大 鄙漏，同層結(jié)點可以不按大小排序，但是上層的節(jié)點比下層節(jié)點大棺蛛。
增加節(jié)點
刪除節(jié)點
因為實現(xiàn)的是優(yōu)先隊列怔蚌，刪除
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) {
//刪除最大結(jié)點是下沉
//**這個操作之前會把最后一個元素賦值給第一個元素 然后讓這個元素下沉到合適位置 而不是直接和第一個最大值比較 （因為這個值是被刪掉的值）**
while(2*k <= N){
int j = 2*k;
if(j < N && less(j, j+1)){
j++;
}
if(!less(k, j)){
//出現(xiàn)后面的值沒有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();
}
