堆排序图解python 堆排序详解

堆排序详解

堆排序是一种经典排序算法，它基于二叉堆来实现。堆排序具有良好的时间复杂度，最坏情况下时间复杂度为O(nlogn)，且具有原地排序的特性，所以在实际应用中得到了广泛的应用。

堆排序图解python

下面我们使用Python程序来图解堆排序的过程。

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

    # Build a maxheap.
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)

我们可以看到，代码中包含了一个`heapify`函数用来调整堆。其作用是从父节点、左节点、右节点中找到最大值并将其置于父节点位置。

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

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

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

    # Change root, if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap

        # Heapify the root.
        heapify(arr, n, largest)

堆排序算法的实现步骤

堆排序的实现步骤如下：

1. 将原始数组构建成一个二叉堆，具体步骤为：从倒数第二层最后一个非叶子节点开始，依次对该节点和其子孙进行调整，使得其以该节点为根节点的子树成为一个大根堆。
2. 将堆顶元素与堆底元素互换，然后将换上来的元素从堆中摘出，并对该元素进行调整。
3. 重复步骤2，直至所有元素均被排序完毕。

代码示例

以下是Python代码示例：

def build_max_heap(arr):
    n = len(arr)
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)
    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):
    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[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

上述代码中，我们定义了三个函数`build_max_heap`、`heap_sort`和`heapify`。`build_max_heap`函数用来构建大根堆。`heap_sort`函数用来实现堆排序。`heapify`函数用来调整堆。

总结

堆排序是一种高效的排序算法，其时间复杂度为O(nlogn)，具有原地排序的特性。它的实现过程相对简单，代码量也较小，非常适合在各种应用场景中使用。