基础树

佚名 6年前 (2019-04-23) 随笔 1508人围观抢沙发百度已收录

树：不包含回路的连通无向图
n个结点 n-1条边
根结点父结点子结点叶结点
内部结点：父、子
深度：根结点到这个结点的层数根为第一层

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

二叉树：每个结点最多有两个儿子左、右儿子
满二叉树、完全二叉树...
满二叉树：二叉树中每个内部结点都有两个儿子深度：h 结点：2^h-1
完全二叉树：除了最右边位置上有一个或者几个叶结点缺少其他丰满
如果一个结点有右子结点，一定有左子结点

完全二叉树：一个父结点：k 左儿子：2*k 右儿子：2*k+1；
左儿子：x 父结点：x/2
N个结点高度为logn
经典应用：堆：神奇的优先队列：最小堆、最大堆

最小堆：所有的父结点都比子结点小

向下调整

void siftdown(int i) { //向下调整 从堆顶向下 
    int t,flag=0;
    while(i*2<=n&&flag==0) { //至少存在左儿子 
        if(h[i]>h[i*2]) t=i*2;
        else t=i;
        if(i*2+1<=n) { //存在右儿子 
            if(h[t]>h[i*2+1]) t=i*2+1;
        }
        if(t!=i) {
            swap(h[t],h[i]);
            i=t;
        }
        else flag=1;
    }
}

向上调整

void siftup(int i) {
    int flag=0;
    if(i==1) return ;
    while(i!=1&&flag==0) {
        if(h[i]<h[i/2]) swap(h[i],h[i/2]);
        else flag=1;
        i/=2;
    }
}

最小堆从小到大排序

#include<iostream>
#include<algorithm>
using namespace std;
int h[101],n;//n为堆的大小
//最小堆 
void siftdown(int i) { //向下调整 从堆顶向下 
    int t,flag=0;
    while(i*2<=n&&flag==0) { //至少存在左儿子 
        if(h[i]>h[i*2]) t=i*2;
        else t=i;
        if(i*2+1<=n) { //存在右儿子 
            if(h[t]>h[i*2+1]) t=i*2+1;
        }
        if(t!=i) {
            swap(h[t],h[i]);
            i=t;
        }
        else flag=1;
    }
}
void creat() {//建堆 
    for(int i=n/2;i>=1;i--) siftdown(i);
}

int deletemax() { //删除最大的元素 
    int t=h[1];
    h[1]=h[n--];
    siftdown(1);//向下调整 
    return t;
}

int main() {
    int num;
    cin>>num;
    for(int i=1;i<=num;i++) cin>>h[i];
    
    n=num; //堆的大小 
    
    creat();//建堆 
    
    for(int i=1;i<=num;i++) //删除顶部元素 把最尾的加到顶 
    cout<<deletemax()<<' ';
    return 0;
}

View Code

最大堆从大到小排序

#include<iostream>
#include<algorithm>
using namespace std;
int h[101],n;//n为堆的大小
//最小堆 
void siftdown(int i) { //向下调整 从堆顶向下 
    int t,flag=0;
    while(i*2<=n&&flag==0) { //至少存在左儿子 
        if(h[i]>h[i*2]) t=i*2;
        else t=i;
        if(i*2+1<=n) { //存在右儿子 
            if(h[t]>h[i*2+1]) t=i*2+1;
        }
        if(t!=i) {
            swap(h[t],h[i]);
            i=t;
        }
        else flag=1;
    }
}
void creat() {//建堆 
    for(int i=n/2;i>=1;i--) siftdown(i);
}
void heapsort() {
    while(n>1) {
        swap(h[1],h[n]);
        n--;
        siftdown(1);
    }
}
int main() {
    int num;
    cin>>num;
    for(int i=1;i<=num;i++) cin>>h[i];
    
    n=num; //堆的大小 
    
    creat();//建堆 
    
    heapsort();
    
    for(int i=1;i<=num;i++) cout<<h[i]<<' ';
    return 0;
}