堆排序的两种建堆方法

堆排序有两种常见的建堆方法：自底向上的方法和自顶向下的方法。

1. 自底向上的建堆方法（Bottom-up Approach）：
这种方法从最后一个非叶子节点开始，依次往前对每个非叶子节点进行堆化操作，直到根节点。堆化操作是将节点与其子节点进行比较并交换，以保持堆的性质。这种方法适用于数组表示的堆结构。

2. 自顶向下的建堆方法（Top-down Approach）：
这种方法从根节点开始，对每个节点依次进行堆化操作，直到叶子节点。堆化操作同样是将节点与其子节点进行比较并交换。这种方法适用于树形表示的堆结构。

无论使用自底向上还是自顶向下的建堆方法，最后得到的都是一个符合堆性质的堆结构。然后可以利用这个堆结构进行排序，即不断取出堆顶元素（最大值或最小值），并将剩余元素重新调整为新的堆结构，直到完成排序。

相关问题

堆排序 python

堆排序（Heap Sort）是一种树形选择排序的方法，是对直接选择排序的有效改进。

堆排序的基本思想是将待排序序列构造成一个大顶堆（或小顶堆），此时整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（或最小值），然后将剩余的n-1个元素重新构造成一个堆，这样就会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。

以下是 Python 代码实现堆排序：

def heapify(arr, n, i):
    largest = i  # 初始化最大元素的下标为父节点i
    l = 2 * i + 1  # 左子节点的下标
    r = 2 * i + 2  # 右子节点的下标

    # 如果左子节点存在且大于父节点，则更新最大元素下标
    if l < n and arr[i] < arr[l]:
        largest = l

    # 如果右子节点存在且大于父节点和左子节点，则更新最大元素下标
    if r < n and arr[largest] < arr[r]:
        largest = r

    # 如果最大元素不是父节点，则交换父节点和最大元素
    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)

    return arr

调用 `heapSort(arr)` 即可对数组 `arr` 进行堆排序。

堆排序的时间复杂度

堆排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。堆排序的过程可以分为两个主要步骤：建堆和排序。

1. 建堆的时间复杂度：
建堆的过程需要从最后一个非叶子节点开始，对每个节点进行堆化操作，使得整个序列构成一个最大堆（或最小堆）。在最坏情况下，每个节点需要进行logn次比较和交换操作，而非叶子节点的数量约为n/2。因此，建堆的时间复杂度为O(n)。

2. 排序的时间复杂度：
在建堆完成后，堆顶元素是序列中的最大值（或最小值）。将堆顶元素与序列末尾元素交换，并将剩余元素重新调整为最大堆（或最小堆）。重复这个过程n-1次，即可得到有序序列。每次调整堆的时间复杂度为logn，总共需要进行n-1次调整。因此，排序的时间复杂度为O(nlogn)。

综上所述，堆排序的时间复杂度为O(nlogn)。