数据结构[堆]

堆是具有下⾯面性质的完全⼆二叉树: 每个结点的值都⼤大于或等于其左右孩⼦子结点的值, 称为⼤大顶堆;如图1; 或者每个结点的值都⼩小于等于其左右孩⼦子的结点的值,称为⼩小顶堆, 如图

堆排序(Heap Sort) 原理理探索

堆排序思路路:
将⽆无需序列列构建成⼀一个堆，根据升序降序需求选择⼤大顶堆或⼩小顶堆
将堆顶元素与末尾元素交换，将最⼤大元素”沉"到数组末端;
重新调整结构，使其满⾜足堆定义，然后继续交换堆顶元素与当前末尾元素，反复 执⾏行行调整+交换步骤，直到整个序列列有序;

堆排序(Heap Sort)代码实现:

堆是具有下⾯面性质的完全二叉树: 每个结 点的值都⼤大于或等于其左右孩⼦子结点的值,称 为大顶堆;

⼆二叉树性质5: 如果对⼀一颗有n个结点的完全⼆二叉树的结点按层序编号,对任⼀一结点i (1 ≤ i ≤ n) 有:
如果 i = 1 ,则结点 i 是⼆二叉树的根. ⽆无双亲. 如果 i > 1,则其双亲是结点 [ i / 2 ];
如果 2i > n ,则结点 i ⽆无左孩⼦子 (结点i 为叶⼦子结点); 否则左孩⼦子是结点 2i;
如果 2i + 1 > n ,则结点 i ⽆无右孩⼦子; 否则其右孩⼦子是结点 2i+1;

堆排序(Heap Sort) — 复杂度分析

//大顶堆调整函数;
/*
 条件: 在L.r[s...m] 记录中除了下标s对应的关键字L.r[s]不符合大顶堆定义,其他均满足;
 结果: 调整L.r[s]的关键字,使得L->r[s...m]这个范围内符合大顶堆定义.
 */
void HeapAjust(SqList *L,int s,int m){
    
    int temp,j;
    //① 将L->r[s] 存储到temp ,方便后面的交换过程;
    temp = L->r[s];
    
    //② j 为什么从2*s 开始进行循环,以及它的递增条件为什么是j*2
    //因为这是颗完全二叉树,而s也是非叶子根结点. 所以它的左孩子一定是2*s,而右孩子则是2s+1;(二叉树性质5)
    for (j = 2 * s; j <=m; j*=2) {
        
        //③ 判断j是否是最后一个结点, 并且找到左右孩子中最大的结点;
        //如果左孩子小于右孩子,那么j++; 否则不自增1. 因为它本身就比右孩子大;
        if(j < m && L->r[j] < L->r[j+1])
            ++j;
        
        //④ 比较当前的temp 是不是比较左右孩子大; 如果大则表示我们已经构建成大顶堆了;
        if(temp >= L->r[j])
            break;
        
        //⑤ 将L->[j] 的值赋值给非叶子根结点
        L->r[s] = L->r[j];
        //⑥ 将s指向j; 因为此时L.r[4] = 60, L.r[8]=60. 那我们需要记录这8的索引信息.等退出循环时,能够把temp值30 覆盖到L.r[8] = 30. 这样才实现了30与60的交换;
        s = j;
    }
    
    //⑦ 将L->r[s] = temp. 其实就是把L.r[8] = L.r[4] 进行交换;
    L->r[s] = temp;
}


//10.堆排序--对顺序表进行堆排序
void HeapSort(SqList *L){
    int i;
   
    //1.将现在待排序的序列构建成一个大顶堆;
    //将L构建成一个大顶堆;
    //i为什么是从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
    for(i=L->length/2; i>0;i--){
        HeapAjust(L, i, L->length);
    }
    
    
    //2.逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
    for(i = L->length; i > 1; i--){
        
        //① 将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
        swap(L, 1, i);
        //② 将L->r[1...i-1]重新调整成大顶堆;
        HeapAjust(L, 1, i-1);
    }
}