简介

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

特点

• 堆：一种特殊的完全二叉树结构
• 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
• 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小

堆排序节点访问

在这里我们借用wiki的定义来说明：

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中

父节点i的左子节点在位置：(2*i+1);

父节点i的右子节点在位置：(2*i+2);

子节点i的父节点在位置：(i-1)//2;

执行步骤

1. 构建堆：将待排序序列构建成一个堆 H[0……n-1]，从最后一个非叶子结点开始，从左至右，从下至上进行调整。根据升序或降序需求选择大顶堆或小顶堆；
2. 此时的堆顶元素，为最大或者最小元素；
3. 把堆顶元素和堆尾元素互换，调整堆，重新使堆有序；
4. 此时堆顶元素为第二大元素；
5. 重复以上步骤，直到堆变空。

动图演示

实例代码

####
# 今日头条：技术好奇心
####

# 构建维护堆
def heapify(arr, n, i):
    # 最大位置
    largest = i
    # left = 2*i + 1
    l = 2 * i + 1
    # right = 2*i + 2
    r = 2 * i + 2

    # 比较父节点与左孩子大小
    if l < n and arr[i] < arr[l]:
        largest = l
    # 比较右孩子与目前的大节点值大小
    # （目前可能是父亲也可能是左孩子）
    if r < n and arr[largest] < arr[r]:
        largest = r

    # 检查上面步骤得出的最大值是否是最初上面定义的父节点
    # 如果不是，则进行交换和递归
    if largest != i:
        # 交换
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归对子树作出调整
        heapify(arr, n, largest)


# 堆排序
def heap_sort(arr):
    # 数组长度
    n = len(arr)

    # 构建大顶堆，由下往上构建所以用-1
    for i in range(n, -1, -1):
        heapify(arr, n, i)

    print('--------- 构建之后的数组内容 ----------')
    print(arr)

    # 一个个交换元素
    for i in range(n - 1, 0, -1):
        # 交换
        arr[i], arr[0] = arr[0], arr[i]
        # 维护交换后的堆
        heapify(arr, i, 0)


if __name__ == "__main__":
    print('今日头条：技术好奇心')
    print('----------- 排序前数组内容 -----------------')
    arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
    print(arr)
    heap_sort(arr)
    print('------------ 排序后的结果 ------------------')
    print(arr)

运行结果：

今日头条：技术好奇心
----------- 排序前数组内容 -----------------
[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
------------ 排序后的结果 ------------------
[1, 2, 3, 7, 17, 19, 25, 26, 36, 90]

相关文章