Python中如何实现堆排序函数？

堆排序是一种常用的排序算法，其基本思想是将待排序的元素构造成一个堆，待排序的元素不断从堆中取出最大（最小）元素，直到堆中的元素为空。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

实现堆排序函数需要先理解堆的概念。堆是一种完全二叉树，其中每个节点的值都大于（或小于）其子节点的值。在堆中，根节点的值是最大（或最小）的。堆可以分为最大堆和最小堆，最大堆中根节点的值最大，最小堆中根节点的值最小。

Python中提供了heapq模块，该模块提供了堆相关的函数。可以使用heapq模块中的函数来实现堆排序函数。

下面是Python中实现堆排序的代码：

import heapq

def heap_sort(arr):
    heap = []
    for num in arr:
        heapq.heappush(heap, num) # 将数组元素插入堆中，自动维护大根堆
    sorted_arr = []
    while heap:
        sorted_arr.append(heapq.heappop(heap)) # 从堆中取出最大元素
    return sorted_arr

代码解释：

- 创建一个空的堆heap。

- 遍历数组arr，将每个元素插入堆heap中。

- 从堆heap中依次取出元素，将其添加到新的列表sorted_arr中。

- 返回排序后的列表sorted_arr。

使用Python的heapq模块可以很方便地实现堆排序函数。该模块提供了很多有用的函数，如heappush、heappop等，可以帮助我们快速地构建堆。同时该模块还可以构建优先队列等数据结构。在学习Python中的数据结构和算法时，heapq模块是一个必须掌握的工具。