算法 二叉树 堆排序

树：
树是指任意两点之间有且仅有一条路径的无向图(即 不包含回路的连通无向图)
树的特点：
1.任意两点有且仅有一条路径
2.如果一个树有n个节点，那么它一定恰好有n-1条边
3.在一个树中加一条边 一定会构成回路

根节点：没有父节点的节点
叶节点：没有子节点的节点
内部节点：既不是根节点也不是叶节点的节点（即 有父亲也有儿子）

二叉树：
二叉树是每一个节点最多只有两个儿子的特殊树左边为左儿子，右边为右儿子

满二叉树：
如果二叉树中每个内部节点都有两个儿子，这样的二叉树称为满二叉树。
它的特性：如果深度为h，则节点数一定为2^h-1;

完全二叉树：若设二叉树的深度为h,则除了第h层外，其余各层(1~h-1)的节点数都达到了最大个数。第h层，
从左到右连续缺少若干节点~

如果完全二叉树的一个节点有右儿子，那它一定有左儿子。
如果完全二叉树的一个父节点为k，那它的左儿子的编号为2k,右儿子为2k+1
如果已知儿子（左儿子或右儿子）的编号为x，那它的父节点的编号为x/2

最小堆：所有父节点都比子节点小（根节点最小）
最大堆：所有父节点都比子节点大（根节点最大）


#pragma mark - - 建堆（最小堆）
/*
 方式一: 以空堆开始，每次向堆中插入一个元素，直到所有的元素插入完毕。（向上调整）时间复杂度O(NlogN)
 方式二: 一维数组可以看作成一个完全二叉树~如果二叉树中每一个节点都满足最小（大）堆,则这个完全二叉树是最小（大）堆。
 叶节点不用处理，所以只要所有非叶节点满足最小（大）堆，那这个完全二叉树是最小（大）堆~ 时间复杂度O(N)
 最后一个非叶节点是n/2
 
 */


void swap(int x,int y,int h[]) {
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    return ;
}

#pragma mark - 方式一
void siftupMin(int i,int h[]) {
    if (i==1) {
        return ;
    }
    int flag = 0; // 标示是否需要继续调整
    while (i!=1 && flag==0) {
        // 判断是否比父节点小
        // 最小堆 父节点比子节点小
        if (h[i]<h[i/2]) {
            swap(i, i/2, h);
        }else {
            flag =1;
        }
        
        i=i/2; // 更新i的编号为父节点的编号 从而方便下一次继续向上调整
    }
}


-(void)createMinHeap1{
    
    int a[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
    int h[15];
    for (int i=1; i<=14; i++) {
        h[i] = a[i];
        siftupMin(i, h);
    }
    
    // 打印最小堆
    printf("\n");
    for (int i=1; i<=14; i++) {
        printf("%5d",h[i]);
    }
    printf("\n\n");
}

#pragma mark - 方式二
void siftdownMin(int i,int h[],int n) {
    int flag=0; // 标示是否需要继续向下调整
    int t=0; // 存储较小的编号
    // 2*i<=n 判断是否有子节点
    while (2*i<=n && flag==0) {
        // 判断左子节点是否比父节点小
        if (h[2*i]<h[i]) {
            t = 2*i;
        }else {
            t = i;
        }
        
        // 判断是否有右子节点
        if (2*i+1<=n) {
            // 判断右子节点是否比当前最小的节点小
            if (h[2*i+1]<h[t]) {
                t=2*i+1;
            }
        }
        
        // 判断i是否等于t
        if (t!=i) {
            // 交换
            swap(i, t, h);
            i = t; // 更新i为t，便于下一次的向下调整
        }else {
            flag =1;
        }
    }
    
}

-(void)createMinHeap2 {
    int h[15]={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
    int n=14;
    
    for (int i=n/2; i>=1; i--) {
        siftdownMin(i, h, n);
    }
    
    // 打印最小堆
    printf("\n");
    for (int i=1; i<=14; i++) {
        printf("%5d",h[i]);
    }
    printf("\n\n");
}


#pragma mark - - 建堆（最大堆）
#pragma mark - 方式一
void siftupMax (int i,int h[]) {
    if (i==1) {
        return ;
    }
    int flag =0 ; // 标示是否需要向上调整
    while (i!=1 && flag==0) {
        if (h[i]>h[i/2]) {
            swap(i, i/2, h);
        }else {
            flag =1;
        }
        i= i/2; // 继续向上调整
    }
}

-(void)createMaxHeap1 {
    int a[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
    int h[15];
    for (int i=1; i<=14; i++) {
        h[i] = a[i];
        siftupMax(i, h);
    }
    
    // 打印最大堆
    printf("\n");
    for (int i=1; i<=14; i++) {
        printf("%5d",h[i]);
    }
    printf("\n\n");
}

#pragma mark - 方式二
void siftdownMax(int i,int h[],int n) {
    int flag=0;
    int t=0; // 记录较大值的编号
    
    while (2*i<=n && flag==0) {
        if (h[2*i] > h[i]) {
            t=2*i;
        }else {
            t=i;
        }
        
        if (2*i+1<=n) {
            if (h[2*i+1] > h[t]) {
                t= 2*i+1;
            }
        }
        
        if (t!=i) {
            swap(i, t, h);
            i=t;
        }else {
            flag =1;
        }
    }
}

-(void)createMaxHeap2 {
    int h[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
    int n=14;
    for (int i=n/2; i>=1; i--) {
        siftdownMax(i, h, n);
    }
    // 打印最大堆
    printf("\n");
    for (int i=1; i<=14; i++) {
        printf("%5d",h[i]);
    }
    printf("\n\n");
    
}

#pragma mark - - 堆排序(从小到大) O(NlogN)
// 删除顶部节点(最小堆)
// 删除顶部节点就是把最后一个节点的值赋值给顶部节点，同时n-1,并向下调整
int n;
int deleteRootMin(int h[]){
    int t;
    t=h[1];
    h[1] = h[n];
    n--;
    siftdownMin(1, h, n);
    return t;
}

-(void)heapsortMin {
    // 建堆（最小堆）
    int h[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
    int m=14;
    n=14;
    for (int i=m/2; i>=1; i--) {
        siftdownMin(i, h, n);
    }
    
    printf("\n");
    for (int i=1; i<=m; i++) {
        printf("%5d",deleteRootMin(h));
    }
    printf("\n\n");
}

#pragma mark - - 堆排序(从大到小)
// 删除顶部节点(最大堆)
// 删除顶部节点就是把最后一个节点的值赋值给顶部节点，同时n-1,并向下调整
int deleteRootMax(int h[]){
    int t;
    t=h[1];
    h[1] = h[n];
    n--;
    siftdownMax(1, h, n);
    return t;
}

-(void)heapsortMax {
    // 建堆（最大堆）
    int h[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
    int m=14;
    n=14;
    for (int i=m/2; i>=1; i--) {
        siftdownMax(i, h, n);
    }
    printf("\n");
    for (int i=1; i<=m; i++) {
        printf("%5d",deleteRootMax(h));
    }
    printf("\n\n");
    
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 疯狂java笔记之树和二叉树
    树的概述 树是一种非常常用的数据结构，树与前面介绍的线性表，栈，队列等线性结构不同，树是一种非线性结构 1.树的定...
    Jack921阅读 4,489评论 1赞 31
  • 二叉树和堆排序
    二叉树 满二叉树 国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，...
    简_爱SimpleLove阅读 4,308评论 0赞 3
  • 数据结构和算法--二叉树的实现
    数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比，二叉树有如下特点： 每个结点最多只有两棵子...
    sunhaiyu阅读 6,531评论 0赞 14
  • 二叉树相关特性与算法
    本文转自 http://www.cnblogs.com/manji/p/4903990.html二叉树-****你...
    doublej_yjj阅读 689评论 0赞 8
  • 算法之二: <<二叉树>>
    1.什么是二叉树？ 在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，...
    zcaaron阅读 1,296评论 2赞 15