【算导】建堆过程时间复杂度分析

以下堆假设都是最大堆。
维护堆的性质的函数:将当前点与左右孩子比较,若孩子更大,将较大的孩子与当前节点交换位置,当前节点被换到的子节点继续用此方法,直到叶节点或不需要交换。
若共有n个元素,则每次调用该方法的时间复杂度为O(lgn)。建堆过程需要自底向上将所有元素都调用一遍该方法,看起来时间复杂度应为O(nlgn),但这个上界虽然正确,却不是渐进紧确的,有很大一部分的节点高度并没有达到lgn。

设n个元素,高度为lgn,堆中高度为h的元素最多有n/2^(h+1)个(h从0开始计数),高度为h的节点调用上述方法的时间复杂度为O(h),则总时间代价为:

等式右边由于在O()内部,所以常数对结果没有影响,所以分母中2的幂数可以改变,变为2^h。根据级数:当|x|<1时:

两边同时微分,并乘以x,得:

将x等于1/2带入,结果为2。
则建堆过程的时间复杂度为

因此可以在线性时间内把一个无序数组构造成一个最大堆。