Python实现堆排序算法

堆排序算法是一种排序算法，它利用堆的特性进行排序。堆是一种数据结构，它可以被看作是一棵完全二叉树。堆排序分为两个步骤：构建堆和堆排序。

构建堆：

在堆排序算法中，我们使用最大堆进行排序。最大堆的定义是，父结点的键值总是大于或等于任何一个子节点的键值。因此，最大堆中根节点的键值就是堆中的最大值。

构建堆的过程是，将给定的序列构建成一个最大堆。从最后一个非叶子节点开始，将每个节点与它的子树进行比较，如果当前节点大于它的子节点，则通过交换节点的位置将其改为一个最大堆。然后，继续向上对每个节点都进行相同的操作，直到根节点。

堆排序：

在构建出一个最大堆之后，我们可以将堆中每个节点的位置与最后一个节点交换。交换之后，堆的大小减一，之后将剩余部分重新构建成最大堆。重复这个操作，直到堆的大小变为 1。

堆排序算法的时间复杂度为 O(nlogn)。

下面是 Python 实现堆排序算法的代码演示：

def heapify(arr, n, i):
    largest = i 
    left = 2 * i + 1      
    right = 2 * i + 2     

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right 

    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i] 

        heapify(arr, n, largest)

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

    for i in range(n, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] 
        heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("排序后")
for i in range(n):
    print("%d" % arr[i])

在上述代码中，heapify() 函数是用来构建最大堆的。在每次构建的过程中，我们先将最大节点初始化为当前节点，然后比较左右子节点与当前节点的大小，并将最大节点位置更新为较大的子节点的位置。如果最大节点不是当前节点，则交换这两个节点，并对新的最大节点所在的子树递归调用 heapify()。

heapSort() 函数首先通过从最后一个非叶子节点开始构建最大堆。然后，将堆顶元素（即最大元素）与数组末尾元素交换。然后，从堆顶开始对堆进行重构，以消除堆中已经被排序的元素。这是由 heapify() 函数完成的。重复这个操作，直到数组排序完成。