介绍一下堆排序

堆排序（Heap Sort）是一种基于完全二叉树的排序算法，它的核心思想是通过建立一个二叉堆（heap）来实现排序。

堆是一种数据结构，它满足以下两个条件：

1. 堆是一棵完全二叉树（除了最后一层，其他层都是满的，最后一层从左到右排列）。

2. 堆中的每个节点都要满足堆的性质，即父节点的值大于（或小于）它的子节点的值，根据父节点的值与子节点的值的大小关系，堆被分为大根堆和小根堆。

堆排序的基本思路是将待排序的序列构建成一个大根堆或小根堆，然后将堆顶元素与堆底元素交换位置，再对剩余的元素重新构建堆，重复此过程直到所有元素都排好序。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，它是一种不稳定的排序算法，因为在交换堆顶元素和堆底元素时可能会破坏相同元素的相对位置关系。

下面是一个简单的堆排序实现代码：

def heap_sort(arr):
    n = len(arr)
    # 构建大根堆
    for i in range(n // 2, -1, -1):
        heapify(arr, n, i)
    # 逐个取出堆顶元素，放到末尾，重新构建堆
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    # 将以i为根节点的子树调整为大根堆
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[largest], arr[i] = arr[i], arr[largest]
        heapify(arr, n, largest)

其中，heapify函数用于将以i为根节点的子树调整为大根堆，heap_sort函数用于构建堆和排序。