算法之最简单的堆笔记

ゝ一纸荒年。 2022-09-24 12:20 125阅读 0赞

公共函数：

比较大小：

private boolean less(Array pq, int i ,int j){
        return pq[i].compareTo(pq[j]) < 0 ;
    }

交换：

private void exch(Array pq , int i , int j ){
        Key t = pq[i] ; 
        pq[i] = pq[j] ;
        pq[j] = t ;
    }

上浮： 当儿大于父，将儿不断向上交换。初始化时一般从N/2位置开始

private void swim(Array pq ,int k){
        while( k>1 && less( k/2, k)){
            exch(pq , k/2 , k);
        }
    }

下沉： 当父小于儿，将父不断向下。初始化时一般从1开始

private void sink(Array pq , int k){
        while (2*k <= N){        //N是pq.length
            int j = 2*k;
            if(j < N && less(j , j+1)) j++;
            if(!less(pq , k , j)) break;
            exch(pq , k , j);
            k = j;
        }
    }

如图：

![Center][]

概念：

每个节点都大于其子节点，这是堆的特性。所以当初始堆不符合这样的特点时候，就需要进行堆的初始化。

![Center 1][]

堆的初始化：

1）堆初始化主要是满足每个父节点大于等于子节点，而叶节点根本没有子节点，所以不考虑叶节点

2）因为不需要考虑叶节点，所以N/2位置一般为截断点

3）遇到不符合特点的节点，通过sink或者swim函数来调整

public void init(){          
        int N = a.length;
        for(int k = 1;k <= N/2;k++){
            sink(a , k)
        }
    }

![Center 2][]

堆的添加：

1）把新增的节点放到最后

2）节点上浮到相应位置即可

public void insert (Array pq , Key v) {
        int N = pq.length;    
        pq[++N] = v;
        swim(pq , N);
    }

![Center 3][]

堆的删除：

1）把要删除的元素与最后叶节点交换位置

2）被交换的叶节点进行下沉操作

3）把要删除的元素为null

public void del(int d , Array pq){
        Key del = pq[d];        
        int N = pq.length;
        exch(pq , d , N--); // 交换最后叶节点与要删除元素位置
        sink(pq , d);       //下沉操作
        pq[N+1] = null;     //要删除元素置null
    }

![Center 4][]

堆的排序：

1）根节点与叶节点互换

2）下沉操作

3）原根节点删除并存入新数组中

4）重复上面操作

while (N > 1) {
        exch(pq , 1 ,N--) ;    // 交换根和最大叶节点位置
        sink(pq , 1);          // 现在根节点下沉操作
    }

![Center 5][]

[Center]: /images/20220719/c479da38213d43aeb2c31dbda8d3d8bb.png
[Center 1]: /images/20220719/4b31445e532349fbb862f50749592033.png
[Center 2]: /images/20220719/432d18a868574262bf4164b8712e8956.png
[Center 3]: /images/20220719/c25a8fb473824b2e9c5a639f5f3297fc.png
[Center 4]: /images/20220719/e47fa6a49af943578bf5dc5582fc0ef7.png
[Center 5]: /images/20220719/4b8f79f0f85a4727b06e4b1d7a38964c.png