排序算法 - 堆排序(Heap Sort)

by LauCyun Aug 02,2014 20:58:57 9,845 views

堆排序通常基于二叉堆实现,以大根堆为例,堆排序的实现过程分为两个子过程。第一步为取出大根堆的根节点(当前堆的最大值), 由于取走了一个节点,故需要对余下的元素重新建堆。重新建堆后继续取根节点,循环直至取完所有节点,此时数组已经有序。基本思想就是这样,不过实现上还是有些小技巧的。

在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:

  1. 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  2. 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
  3. 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

其中步骤1是给步骤2和3用的。

图1 堆排序

建堆时可以自顶向下,也可以采取自底向上,以下先采用自底向上的思路分析。我们可以将数组的后半部分节点想象为堆的最下面的那些节点,由于是单个节点,故显然满足二叉堆的定义,于是乎我们就可以从中间节点向上逐步构建二叉堆,每前进一步都保证其后的节点都是二叉堆,这样一来前进到第一个节点时整个数组就是一个二叉堆了。

堆排在空间比较小(嵌入式设备和手机)时特别有用,但是因为现代系统往往有较多的缓存,堆排序无法有效利用缓存,数组元素很少和相邻的其他元素比较,故缓存未命中的概率远大于其他在相邻元素间比较的算法。但是在海量数据的排序下又重新发挥了重要作用,因为它在插入操作和删除最大元素的混合动态场景中能保证对数级别的运行时间。

 

1 算法实现

C

#include <stdio.h>


#define ElemType int

void Show(ElemType *, const int);
void Swap(ElemType *, ElemType *);
void MaxHeapify(ElemType arr[], int start, int end);
void HeapSort(ElemType arr[], int len);


void Show(ElemType *array, const int len) {
    for (int i = 0; i < len; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

void Swap(ElemType *a, ElemType *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

void MaxHeapify(ElemType arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int parent = start;
    int son = parent * 2 + 1;
    while (son <= end) { //若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小,选择最大的
            son++;
        if (arr[parent] > arr[son]) //如果父节点大于子节点代表调整完毕,直接跳出函数
            return;
        else { //否则交换父子内容再继续子节点和孙节点比较
            Swap(&arr[parent], &arr[son]);
            parent = son;
            son = parent * 2 + 1;
        }
    }
}

void HeapSort(ElemType arr[], int len) {
    int i;
    // 初始化,i从最后一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--) {
        MaxHeapify(arr, i, len - 1);
        // Show(arr, len);
    }
    // 先将第一个元素和已排好元素前一位做交换,再从新调整,直到排序完毕
    for (i = len - 1; i > 0; i--) {
        Swap(&arr[0], &arr[i]);
        MaxHeapify(arr, 0, i - 1);
        // Show(arr, len);
    }
}


int main(int argc, char *argv[]) {
    ElemType arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int len = (int) sizeof(arr) / sizeof(*arr);
    HeapSort(arr, len);
    Show(arr, len);
    return 0;
}

Python

#!/usr/bin/env python
# -*-coding:utf-8-*-


def heap_sort(alist):
    def max_heapify(start, end):
        """
            调整最大堆
        :param start: 开始位置
        :param end: 结束位置
        :return: 
        """
        parent = start  # 父节点
        while True:
            child = 2 * parent + 1  # 子节点
            # 子节点在范围内才做比较
            if child > end:
                break
            # 先比较两个子节点大小,选择最大的
            if child + 1 <= end and alist[child] < alist[child + 1]:
                child += 1

            # 比较父子节点
            if alist[parent] > alist[child]:  # 如果父节点大于子节点代表调整完毕,直接跳出函数
                break
            else:  # 否则交换父子内容再继续子节点和孙节点比较
                # print("parent={p}, child={c}".format(p=parent, c=child))
                # print("before: %s" % alist)
                alist[parent], alist[child] = alist[child], alist[parent]
                # print("after : %s" % alist)
                parent = child

    # 创建最大堆
    # print("Build Max Heap:")
    for start in range((len(alist) - 2) // 2, -1, -1):
        max_heapify(start, len(alist) - 1)

    # 堆排序
    # print("\nHeap Sort:")
    for end in range(len(alist) - 1, 0, -1):
        # print("end=%s" % end)
        # print(alist)
        alist[0], alist[end] = alist[end], alist[0]
        max_heapify(0, end - 1)
    return alist


unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
print(heap_sort(unsortedArray))

 

2 算法过程演示

如果显示不正常,请戳这里

输出如下所示:

$ python3.5 heap_sort.py
Build Max Heap:
parent=3, child=7
before: [6, 5, 3, 1, 8, 7, 2, 4]
after : [6, 5, 3, 4, 8, 7, 2, 1]
parent=2, child=5
before: [6, 5, 3, 4, 8, 7, 2, 1]
after : [6, 5, 7, 4, 8, 3, 2, 1]
parent=1, child=4
before: [6, 5, 7, 4, 8, 3, 2, 1]
after : [6, 8, 7, 4, 5, 3, 2, 1]
parent=0, child=1
before: [6, 8, 7, 4, 5, 3, 2, 1]
after : [8, 6, 7, 4, 5, 3, 2, 1]


Heap Sort:
end=7
[8, 6, 7, 4, 5, 3, 2, 1]
parent=0, child=2
before: [1, 6, 7, 4, 5, 3, 2, 8]
after : [7, 6, 1, 4, 5, 3, 2, 8]
parent=2, child=5
before: [7, 6, 1, 4, 5, 3, 2, 8]
after : [7, 6, 3, 4, 5, 1, 2, 8]

end=6
[7, 6, 3, 4, 5, 1, 2, 8]
parent=0, child=1
before: [2, 6, 3, 4, 5, 1, 7, 8]
after : [6, 2, 3, 4, 5, 1, 7, 8]
parent=1, child=4
before: [6, 2, 3, 4, 5, 1, 7, 8]
after : [6, 5, 3, 4, 2, 1, 7, 8]

end=5
[6, 5, 3, 4, 2, 1, 7, 8]
parent=0, child=1
before: [1, 5, 3, 4, 2, 6, 7, 8]
after : [5, 1, 3, 4, 2, 6, 7, 8]
parent=1, child=3
before: [5, 1, 3, 4, 2, 6, 7, 8]
after : [5, 4, 3, 1, 2, 6, 7, 8]

end=4
[5, 4, 3, 1, 2, 6, 7, 8]
parent=0, child=1
before: [2, 4, 3, 1, 5, 6, 7, 8]
after : [4, 2, 3, 1, 5, 6, 7, 8]

end=3
[4, 2, 3, 1, 5, 6, 7, 8]
parent=0, child=2
before: [1, 2, 3, 4, 5, 6, 7, 8]
after : [3, 2, 1, 4, 5, 6, 7, 8]

end=2
[3, 2, 1, 4, 5, 6, 7, 8]
parent=0, child=1
before: [1, 2, 3, 4, 5, 6, 7, 8]
after : [2, 1, 3, 4, 5, 6, 7, 8]

end=1
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

分析得知:首先是创建最大堆(Build_Max_Heap),将堆所有数据重新排序,如图2

图2 Build Max Heap

接着,就是堆排序(HeapSort),移除位在第一个数据的根节点,并做最大堆调整的递归运算,如图3

图3 Heap Sort

 

3 复杂度分析

从代码中可以发现堆排最费时间的地方在于构建二叉堆的过程。

上述构建大根堆和小根堆都是自底向上的方法,建堆过程时间复杂度为\(O(2n)\), 堆化过程(可结合图形分析,最多需要调整的层数为最大深度)时间复杂度为\( \log i\) 故堆排过程中总的时间复杂度为\( O(n \log n)\)

先看看建堆的过程,画图分析(比如以8个节点为例)可知在最坏情况下,每次都需要调整之前已经成为堆的节点,那么就意味着有二分之一的节点向下比较了一次,四分之一的节点向下比较了两次,八分之一的节点比较了三次......等差等比数列求和,具体过程可参考下面的链接。

所以,堆排序的最优、最坏和平均时间复杂度都为\({\displaystyle O(n\mathrm {log} n)}\),空间复杂度为\({\displaystyle O(1)}\)

 

4 参考文档

(全文完)

Tags