【算法笔记】用指针实现小顶堆

本文将讨论指针堆与数组堆的区别，和指针堆的具体实现方式。

题目：洛谷P3378

啊对了，下文不会解释指针是什么、指针的用法、为什么加“&”等基础问题，需要的建议去看《算法竞赛入门经典训练指南》中指针版名次数(treap)的实现，或是向懂的小伙伴提问。

一 指针与数组的比较

数组版中，由于下标的特殊性质，我们可以快速找到某个节点的父亲节点。所以在数组版中，大多使用的是从叶子往根节点更新的插入/删除方式。同时，数组版的原理是对数组中最后一个有效位置进行替换后重新维护树的性质，也就是说，在每次操作过后，堆中新增或删去的点一定是完全二叉树的最后一个点，这就保证了其永远是一棵完全二叉树，而不会退化，也就有了稳定的logM效率(M指堆中的数的个数)。

但是与之相比，指针版没法通过下标直接查找父节点和子节点，也无法直接翻出完全二叉树的最后一个点。(其实也不是完全不行，如果硬要实现的话，需要维护大量的额外的变量，如父节点指针、最后节点指针，这里不做赘述，直接模仿数组版打就行了。个人认为这种玩指针的方法并不优雅，当然我后面提到的也优雅不到哪去就是了。)所以指针版的实现需要从root节点开始，用递归的方式对树进行操作。同时由于无法确定最后节点，要维持完全二叉树的形态就变得复杂(删除过程中可能出现二叉树退化却难以复原的问题)。指针的优势大概在于，其可以动态的申请和释放空间，还有优雅和简洁吧，不需要数组版复杂的讨论过程。

或许指针的常数会比数组的大点？

二 指针(递归)版思路

首先，通过其他的文章我们可以知道，二叉堆(以下默认讨论小顶堆)有几个重要的性质：一是每个节点权值小于左右子节点的权值，二是二叉树深度为logN(这是复杂度的前提)。

接下来我们考虑如何实现加入新节点。

这里先放一段代码

            inline void _insert(node*&u,int x){
        if(!u) u=new node(x);
        else{
            if(x<u->x) swap(x,u->x);
            int nex=u->check();
            _insert(u->ch[nex],x);
            u->maintain();
        }
    }

    

先不去理会性质一，我们如何在不断添加新节点的过程中保证其是或尽量维持为一棵完全二叉树，也就是：多出来的节点何去何从的问题。这个问题对于数组版来说可以无视，因为人家直接把下标往后挪一下就是构造完全二叉树的下一个点了，但是指针版就需要在每一步的递归中判断这个点在左子树还是右子树，然后一步一步往下走。

一开始，我直接通过左右子树是否为满二叉树判断:如果左子树为满二叉树，右子树未满，那就说明这个新节点应该加在右子树；如果左子树未满，节点加左子树；左右都满，节点加左子树。(可以画图理解)但是后来发现，这种方法只有在严格按顺序加入节点时有用，经过几轮的删除操作后可能会出现左右子树大小不等但都是满二叉树的状况。下面是这种错误的写法：

        struct node{
        int x; bool f; node *ch[2];
        node(int p=0){
            //we think a no_child tree as a not full one
            x=p; f=0; ch[0]=ch[1]=NULL;
        }
        inline int check(){
            //use to find the not full tree  if full return left
            //deal the leaf
            if(!ch[0]) return 0; if(!ch[1]) return 1; 
            //deal the mid root
            if(ch[0]->f&&ch[1]->f) return 0;
            return ch[0]->f?1:0;
        }
        inline void maintain(){
            //maintain the full tag
            if(!ch[0]||!ch[1]) f=0;
            else f=!(ch[0]->f^ch[1]->f);
        }
    }

    

这种写法使我TLE了三个点。于是我考虑了下面的写法：维护每个节点的树的大小，左右子树不等大时，新节点应该往小的子树加。如下：

        struct node{
        int x,c; node *ch[2];
        node(int p=0){
            x=p; c=1; ch[0]=ch[1]=NULL;
        }
        inline int check(){
            if(!ch[0]) return 0; 
            if(!ch[1]) return 1; 
            if(ch[0]->c<=ch[1]->c) return 0;
            return 1;
        }
        inline void maintain(){
            c=1;
            if(ch[0]) c+=ch[0]->c;
            if(ch[1]) c+=ch[1]->c;
        }
    }

    

这种做法反而更好理解。满二叉树的左右子树节点应该是一样多的，那么只要不断维护这一点，自然可以趋向一棵满二叉树进而维持logN的深度。

至于性质一的维护。反正我们只需要把这个值加到堆里就行了，所以在递归过程中找到一个合适的位置就直接把值swap进去，原来的值取出来，再为取出来的这个值找一个新位置...直到新叶子节点建立。

删除的原理与数组版也把不太一样，是通过不断下移根数值(就是那个最小值)到叶子节点，然后将这个叶子节点删除。但是递归的删除方式就没有办法像这样一路兼顾着满二叉树的要求往下走了，需要注意，堆之所以能找出最小值并维护，就在于其根点权大于左右子点权的性质，所以我们需要优先维护这一点。也就是说根数值往下走的过程中，可以与之替换的只能是左右儿子中较小的那个值。

            inline void _delete(node*&u){
        if(!u->ch[0]&&!u->ch[1]){
            delete u; u=NULL;
        }else{
            if(!u->ch[0]){
                swap(u->ch[1]->x,u->x);
                _delete(u->ch[1]);
            }else if(!u->ch[1]){
                swap(u->ch[0]->x,u->x);
                _delete(u->ch[0]);
            }else{
                REG int nex=u->ch[0]->x<u->ch[1]->x?0:1;
                swap(u->ch[nex]->x,u->x);
                _delete(u->ch[nex]);
            }
            u->maintain();
        }
        
    }

    

这也就注定了连续的删除操作会给二叉树的形状增加不确定性，可能形成上面错误做法中伪满二叉树。好在我们使用了维护节点数量的方法，可以在加入新节点的过程中慢慢修复这棵完全二叉树，但修复过程的这棵树不会是最优的，也就是说如果将堆中节点个个数视为N，在删去了k个数，往里面重新补入新的数时，其复杂度不是log(N-k)，而会在log(N-k)到logN之间波动。这是与数组版雷打不动的log(N-k)不同的。

下面是完整代码。

        #include <cstdio>
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
inline void swap(int &a,int &b){
    REG int t=a; a=b; b=t;
}
const int N=1e6+9;
struct Heap{
    struct node{
        int x,c; node *ch[2];
        node(int p=0){
            x=p; c=1; ch[0]=ch[1]=NULL;
        }
        inline int check(){
            if(!ch[0]) return 0; 
            if(!ch[1]) return 1; 
            if(ch[0]->c<=ch[1]->c) return 0;
            return 1;
        }
        inline void maintain(){
            c=1;
            if(ch[0]) c+=ch[0]->c;
            if(ch[1]) c+=ch[1]->c;
        }
    }*root;
    Heap():root(NULL){}
    inline void _insert(node*&u,int x){
        if(!u) u=new node(x);
        else{
            if(x<u->x) swap(x,u->x);
            REG int nex=u->check();
            _insert(u->ch[nex],x);
            u->maintain();
        }
    }
    inline int _top(){ return root->x; }
    inline void _delete(node*&u){
        if(!u->ch[0]&&!u->ch[1]){
            delete u; u=NULL;
        }else{
            if(!u->ch[0]){
                swap(u->ch[1]->x,u->x);
                _delete(u->ch[1]);
            }else if(!u->ch[1]){
                swap(u->ch[0]->x,u->x);
                _delete(u->ch[0]);
            }else{
                REG int nex=u->ch[0]->x<u->ch[1]->x?0:1;
                swap(u->ch[nex]->x,u->x);
                _delete(u->ch[nex]);
            }
            u->maintain();
        }
        
    }
}Q;
inline char getc(){
    static char buf[1<<18],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
}
inline int scan(){
    REG int x=0; REG char ch=0;
    while(ch<48) ch=getc();
    while(ch>=48) x=x*10+ch-48,ch=getc();
    return x;
}
inline void print(int x){
    if(x>9){
        print(x/10);
        putchar(x%10+48);
    }else putchar(x+48);
}
int main(){
    REG int n=scan(),op,x;
    while(n--){
        op=scan();
        switch(op){
        case 1:
            x=scan(); Q._insert(Q.root,x);
            break;
        case 2:
            print(Q._top()); putchar(‘\n‘);
            break;
        default:
            Q._delete(Q.root);
            break;
        }
    }
    return 0;
}

    

原文：https://www.cnblogs.com/Qing-LKY/p/Heap-with-pointer.html