堆排序

什么是堆

1. 堆特性（Heap Property）：在堆中，对于每个节点X，X 的父节点的值总是大于等于（或小于等于）其子节点的值。这个性质决定了堆的结构。

2. 完全二叉树特性：堆通常使用一维数组来表示完全二叉树的结构，即父节点和子节点之间的关系由数组中的索引关系来表示。通过这种表示，可以将堆的元素有效地存储在数组中，并且可以在不需要指针的情况下在树中进行导航。

1. 最大堆（Max Heap）：在最大堆中，父节点的值总是大于等于其子节点的值。因此，根节点是堆中的最大值。

2. 最小堆（Min Heap）：在最小堆中，父节点的值总是小于等于其子节点的值。因此，根节点是堆中的最小值。

堆的操作

1. 上滤（Percolate-Up）：当在堆中插入一个新元素时，新元素通常被放置在堆的最后一个位置（数组的末尾）。为了维护堆的性质，即父节点的值大于等于（或小于等于）其子节点的值，需要将新元素向上移动至合适的位置。具体过程如下：
• 将新元素放置在堆的最后一个位置（数组末尾）。
• 比较新元素与其父节点的值。如果新元素的值大于（或小于）其父节点的值，则交换新元素与父节点的位置。
• 继续向上比较并交换，直到新元素达到合适的位置或成为根节点为止。
上滤操作保证了新插入的元素在堆中找到了正确的位置，同时维持了堆的性质。

2. 下滤（Percolate-Down）：当从堆中删除根节点后，为了维持堆的性质，需要将最后一个元素（通常是原来堆的最后一个元素）移动到根节点的位置。然后，需要将这个新的根节点向下移动至合适的位置。具体过程如下：
• 将最后一个元素（原来堆的最后一个元素）移动到根节点的位置。
• 比较新的根节点与其子节点的值。如果新的根节点的值小于（或大于）其子节点的值，则与其中较大（或较小）的子节点交换位置。
• 继续向下比较并交换，直到新的根节点达到合适的位置或没有子节点为止。
下滤操作保证了新的根节点在堆中找到了正确的位置，同时维持了堆的性质。

堆排序

1. 构建堆：将待排序的数组看作是一个完全二叉树，通过从最后一个非叶子节点开始，依次进行下滤操作，将数组转换为一个最大堆（或最小堆）。这一步骤将花费O(n)的时间复杂度。

2. 排序：在构建好的堆中，根节点是最大（或最小）的元素。将根节点与堆的最后一个元素交换位置，然后排除掉最后一个元素（它已经是有序的），再对剩余的元素进行一次下滤操作，重新调整堆。这样，每次从堆中取出一个最大（或最小）元素，并将其放置到数组的末尾。重复这个过程直到堆为空，即所有元素都已排序。

// 堆排序
HeapSort(arr):
    n = 数组长度
    // 构建最大堆（或最小堆）
    for i from n/2-1 to 0:
        PercolateDown(arr, n, i)

    // 排序
    for i from n-1 to 0:
        交换 arr[0] 和 arr[i]
        PercolateDown(arr, i, 0)

// 下滤操作
PercolateDown(arr, n, i):
    largest = i
    left_child = 2*i + 1
    right_child = 2*i + 2

    // 找出左子节点和右子节点中较大（或较小）的节点
    if left_child < n and arr[left_child] > arr[largest]:
        largest = left_child
    if right_child < n and arr[right_child] > arr[largest]:
        largest = right_child

    // 如果较大（或较小）的节点不是当前节点，交换节点并递归进行下滤操作
    if largest != i:
        交换 arr[i] 和 arr[largest]
        PercolateDown(arr, n, largest)