堆排序的时间复杂度

发表于   |   分类于   |  

作者ChihMinh，原作链接https://chihminh.github.io/2016/08/08/heap-sort/，转载请注明出处

以前误认为建堆的时间复杂度是O(nlog n)，想的很简单，每一次堆调整的时间复杂度为O(log n)，n个节点的时间复杂度为O(nlog n)，待真的好好计算一番才发现是错的。下面根据堆排序的完整过程来计算一些时间复杂度。

堆：满足堆有序的完全二叉树。
堆有序：对一棵二叉树的所有父节点大于等于（最大堆）或者小于等于（最小堆）其全部子节点。
假设堆有n个节点，树的高度为h=floor(log n)（floor(a)表示不超过a的最大整数）。
以下的三个方法源码来自维基百科 。

堆排序的过程

用数组存储堆（本文默认是最大堆），如果从下标0开始的话，节点k的父节点为floor((k-1)/2)，节点k的左、右子节点为2k+1和2k+2。
对于一个未排序的初始化数组，从其最后一个父节点开始往前进行堆调整，这样建好最大堆每次取其根节点作为最大值，把最后一个节点作为新的根结点对堆进行调整，反复进行上述操作直至堆只有一个根节点。

堆调整

首先来看看堆调整过程，对于节点index，递归和其子节点比较并互换使其满足最大堆（比较两次，移动一次）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void maxHeapify(int[] data, int heapSize, int index){
    // 当前点与左右子节点比较
    int left = getChildLeftIndex(index);
    int right = getChildRightIndex(index);        
    int largest = index;
    if (left < heapSize && data[index] < data[left]) {
        largest = left;
    }
    if (right < heapSize && data[largest] < data[right]) {
        largest = right;
    }
    //得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
    if (largest != index) {
        int temp = data[index];
        data[index] = data[largest];
        data[largest] = temp;
        maxHeapify(data, heapSize, largest);
    }
}

建立最大堆：

建立最大堆就是从一个完全二叉树的最后一个父节点开始往前进行堆调整。若最后一个节点为n-1，那么其父节点（也就是最后一个父节点）为floor(((n-1)-1)/2)。

1
2
3
4
5
6
7
8
private static void buildMaxHeapify(int[] data){
    //没有子节点的才需要创建最大堆，从最后一个的父节点开始
    int startIndex = getParentIndex(data.length - 1);
    //从尾端开始创建最大堆，每次都是正确的堆
    for (int i = startIndex; i >= 0; i--) {
        maxHeapify(data, data.length, i);
    }
}

堆排序

所谓堆排序就是每次取堆的根结点为最大值，然后将最后一个节点作为根节点，进行堆调整，堆排序的时间等于建堆和进行堆调整的时间，所以堆排序的时间复杂度是O(nlog n + n) =O(nlog n)。

1
2
3
4
5
6
7
8
9
private static void heapSort(int[] data) {
    //末尾与头交换，交换后调整最大堆
    for (int i = data.length - 1; i > 0; i--) {
        int temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        maxHeapify(data, i, 0);
    }
}

堆调整的时间复杂度

从堆调整的代码可以看到是当前节点与其子节点比较两次，交换一次。父节点与哪一个子节点进行交换，就对该子节点递归进行此操作，设对调整的时间复杂度为T(k)（k为该层节点到叶节点的距离），那么有
T(k)=T(k-1)+3, k∈[2,h]
T(1)=3
迭代法计算结果为：
T(h)=3h=3floor(log n)
所以堆调整的时间复杂度是O(log n) 。

建堆的时间复杂度

n个节点的堆，树高度是h=floor(log n)。对深度为于h-1层的节点，比较2次，交换1次，这一层最多有2^(h-1)个节点，总共操作次数最多为3(12^(h-1))；对深度为h-2层的节点，总共有2^(h-2)个，每个节点最多比较4次，交换2次，所以操作次数最多为3(22^(h-2))……
以此类推，从最后一个父节点到根结点进行堆调整的总共操作次数为：

1
2
3
4
s=3*[2^(h-1) + 2*2^(h-2) + 3*2^(h-3) + … + h*2^0]       a
2s=3*[2^h + 2*2^(h-1) + 3*2(h-2) + … + h*2^1]           b
b-a，得到一个等比数列，根据等比数列求和公式
s = 2s - s = 3*[2^h + 2^(h-1) + 2^(h-2) + … + 2 - h]=3*[2^(h+1)-  2 - h]≈3*n

所以建堆的时间复杂度是O(n)。