堆排序算法详解：原理、步骤及Python实现

堆排序是一种基于堆的排序算法，它通过将待排序序列构建成一个堆，然后不断将堆顶元素与堆中最后一个元素交换，并调整堆结构，使得每次交换后的堆仍是一个合法的堆，直到整个序列按照从小到大的顺序排列好。

具体算法描述如下：

1. 将待排序序列构建成一个堆，通常使用大根堆（即父节点的值大于等于子节点的值）或小根堆（即父节点的值小于等于子节点的值）。

2. 循环执行以下步骤，直到整个序列按照从小到大的顺序排列好：

   a. 将堆顶元素与堆中最后一个元素交换，即将最大值（大根堆）或最小值（小根堆）放到序列的末尾。

   b. 调整堆结构，使得剩余元素仍是一个合法的堆。

3. 排序完成后，序列按照从小到大的顺序排列好。

具体实现时，我们可以使用数组来表示堆，根据堆的性质，可以得到以下几个重要的操作：

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)

其中，heapify函数用于调整堆结构，heap_sort函数用于排序。