模板 堆

发表于 | 分类于 |
字数统计: 695 字

堆包括二叉堆，二项堆，可并堆，斐波那契堆，等。

普通二叉堆

最经典的堆结构。其本身为一颗完全二叉树，并且每一个节点都遵循着自身的值大于（或者小于）父节点的值的规律。至于出现重复的值该怎么办，这就要具体情况具体分析。
一般而言不需要手写二叉堆，使用C++自带的即可。

以下操作默认为小根堆：

上浮操作

让当前位置为$id$的节点不断与其父节点比较，若其比父节点大则符合小根堆的标准，停止上浮；若其小于父节点则与父节点相交换，实现上浮。

1
2
3
4
5
6
7
8
9
10
void pushup(int *h, int id){
    int tmp = h[id];
    while(id >= 1){
        int par = id >> 1;
        if(h[par] < tmp)
            break;
        h[id] = h[par], id >>= 1;
    }
    h[id] = tmp;
}

下沉操作

让当前位置为$id$的节点不断与其子节点比较，边界是其自身为叶子。
若其只有一个子节点，且其小于子节点则符合堆的要求，停止下沉；否则其与子节点交换，下沉。
若其有两个子节点且小于两个子节点，则停止下沉；否则让更小的那个子节点与自身交换，下沉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void pushdown(int *h, int id){//下称操作
    int tmp = h[id];
    while(id <= (n >> 1)){
        int lson = id << 1, rson = id << 1 | 1;
        if(rson > n){
            if(tmp < h[lson])
                break;
            else 
                h[id] = h[lson], id = lson;
        }else{
            if(tmp < h[lson] && tmp < h[rson])
                break;
            else {
                if(h[lson] < h[rson])
                    h[id] = h[lson], id = lson;
                else
                    h[id] = h[rson], id = rson;
            }
        }
    }
    h[id] = tmp;
}

插入操作

将新数$val$插入堆的最底层中，从左到右第一个空出的位置（即堆的最后一个位置的后面）。然后执行上浮操作。

1
2
3
4
5
void pushin(int *h, int val){//增加数操作
    int id = ++n;
    h[id] = val;
    pushup(h, id);
}

弹出操作

将堆最后一个位置的节点与根节点交换，删去最后一个位置的节点，然后让根下沉。

1
2
3
4
5
6
int popout(int *h){
    int top = heap[1];
    heap[1] = heap[n--];
    pushdown(h, 1);
    return top;
}

建堆操作

从底到顶，一层一层对非叶子节点进行下沉操作。

1
2
3
4
void build_heap(int *h, int n){//建堆
    for(int i = n >> 1; i >= 1; --i)
        pushdown(heap, i);
}

斐波那契堆

斐波那契堆是一种可并堆，虽然其的写法比较复杂，但是其的摊还时间复杂度比较优秀。许多操作可以做到平摊$O(1)$的时间复杂度。
确切地说，一个斐波那契堆是一个具有最小堆序的有根树森林。