leetcode堆排序

堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为 O(nlogn)。堆排序分为两个阶段：建堆和排序。建堆的时间复杂度为 O(n)，排序的时间复杂度为 O(nlogn)。

具体实现步骤如下：
1. 将待排序序列构建成一个大根堆（或小根堆），此时整个序列的最大（或最小）值就是堆顶的根节点。
2. 将堆顶元素与末尾元素交换，将最大（或最小）元素“沉”到数组末端。
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

代码实现如下：

def heap_sort(nums):
    n = len(nums)
    # 构建大根堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(nums, n, i)
    # 排序
    for i in range(n - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        heapify(nums, i, 0)

def heapify(nums, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and nums[left] > nums[largest]:
        largest = left
    if right < n and nums[right] > nums[largest]:
        largest = right
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i]
        heapify(nums, n, largest)