[游戏开发]堆排序时间复杂度计算

堆排序传入两个参数arr 以及当前arr截取的需要排序的长度n
首先是进行建堆，第二步将末尾结点替换根结点，对长度截取数n减去1再进行建堆
代码如下：

function heapify(arr,n,i){
    //arr数组 n表示当前堆大小也就是arr截取的长度 i表示当前维护的三角堆顶下标
    let left = i * 2 + 1;
    let right = i * 2 + 2;
    let maxindex = i;
    if(left<n&&arr[maxindex]<arr[left]){
        maxindex = left;
    } 
    if(right<n&&arr[maxindex]<arr[right]){
        maxindex = right;
    }
    if(i!=maxindex){
        let temp = arr[i];
        arr[i] = arr[maxindex];
        arr[maxindex] = temp;
        heapify(arr,n,maxindex);//交换完成后 maxindex所在位置的堆结构被破坏 所以对该堆递归
    }
}

function heapSort(arr,n){
    //建堆
    for(let i=Math.floor(n/2-1);i>=0;i--){
        //n/2-1也就是找到末尾节点的父节点下标，因为n代表总长度,末尾下标为n-1 对应的父节点下标为(n-1-1)/2
        heapify(arr,n,i);
    }
    //将堆顶和最后一个元素位置交换,并将其拆出来
    for(let i = n-1;i>=0;i--){
        let temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        heapify(arr,i,0);//将最后一个元素排除并建堆
    }
}

时间复杂度计算分析：
建堆时间复杂度(O(n))：
设数组长度为n，层数为h(为了方便理解，h从1计算)
假设是一个满二叉树，则3层就有7个节点，4层有11个…所以n = 2^h - 1
从最底部分析，(第一层1个第二层2个第三层4个第h层2^(h-1)个)
倒数第1层节点的父节点最多下调1次，倒数第1层共有2^(h-1)个节点
倒数第2层节点的父节点最多下调2次，倒数第2层共有2^(h-2)个节点
…
倒数第h-1层（第2层）节点的父节点最多下调h-1次，倒数第h-1层共有2个节点
所以从倒数第一层开始计算

t = 1 * 2^(h-1) + 2 * 2^(h-2) + 3 * 2^(h-3)…+ (h-1) * 2^1

由公式可看出，下调次数就是当前节点所在层数能够下探的层数。
假设4层的满二叉树，则对于第3层，还有1层下探空间，所以才说第4层的父节点(第3层)最多下调1次
所以第2层的父节点(根节点)最多下调h-1次
每层的计算为：最大下调次数 * 当前层节点个数
总结下来每层(从第2层开始算)的计算公式(假设当前第i层(i从1计算)，总层数h)为 (h-i) * 2^(i-1)
现在需要t和h的关系
通过高中数学计算2t-t = 2^1 + 2^2 + 2^3 + … + 2^(i-1) + (h-i)*2^i - (h-1) * 2 = 2^i -2i
又因为总节点数n = 2^i - 1 所以i = log(n+1)
所以t = 2^log(n+1) - 2log(n+1) 忽略掉后者，t = n + 1
所以建堆时间复杂度O(n)

交换尾结点与根节点时间复杂度(O(nlogn))
和建堆的思路差不多，交换节点为O(1)交换n次，所以遍历消耗时间O(n),最坏情况下，对n-1个节点建堆的过程中，耗时为O(logn)，所以耗时为n*log(n)

因此总耗时为O(n) + O(nlogn),考虑n>=2时，logn比1大，所以最终取时间复杂度为O(nlogn)

上述进行的计算在思路上参考了众多其他文章，思路上大同小异，若有误希望大家指出。