请阐述堆排序的基本概念并给出具体的实现代码。堆排序是如何工作的？如何实现堆排序算法？

解答思路：

堆排序是一种基于二叉堆的比较排序算法。它利用堆这种数据结构的特点，通过构建最大堆或最小堆，实现数据的排序。其核心思想是将待排序的序列构造成一个大顶堆或小顶堆，通过不断交换堆顶元素与末尾元素的方式，将最大（或最小）元素移动到序列末尾，并逐步缩小堆的大小，最终实现整个序列的排序。

最优回答：

堆排序的实现过程大致如下：

1. 构建初始堆（通常使用最大堆）。这可以通过比较相邻元素并进行交换来实现，以确保父节点的值大于或等于其子节点的值。
2. 将堆顶元素（即最大值）与最后一个元素交换，并删除堆顶元素。此时，最大元素已经移动到序列末尾。
3. 调整剩余元素以重新构建堆。通过反复上浮和下沉元素来确保堆的性质（即满足堆的定义）。
4. 重复步骤2和步骤3，直到堆为空。此时，整个序列已经按照升序排列。

代码实现示例（以最大堆为例）：

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child index
    right = 2 * i + 2  # Right child index

    # Check if left child of root exists and is greater than root
    if left < n and arr[i] < arr[left]:
        largest = left

    # Check if right child of root exists and is greater than root's current largest child
    if right < n and arr[largest] < arr[right]:
        largest = right

    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        heapify(arr, n, largest)  # Heapify the root of the subtree rooted with largest

def heapSort(arr):
    n = len(arr)

    # Build heap (rearrange array)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements from heap
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap arr[0] with the last element in heap (min heap)
        heapify(arr, i, 0)  # Heapify the reduced heap after removing an element from it