欢迎大家来到IT世界,在知识的湖畔探索吧!

简介

堆排序（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)

欢迎大家来到IT世界,在知识的湖畔探索吧!

运行结果：

欢迎大家来到IT世界,在知识的湖畔探索吧!今日头条：技术好奇心
----------- 排序前数组内容 -----------------
[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
------------ 排序后的结果 ------------------
[1, 2, 3, 7, 17, 19, 25, 26, 36, 90]

相关文章