第七章 排序（堆排序）

说明

​ 堆排序（Heap Sort）是一种基于二叉堆数据结构的比较型排序算法。它是一种选择排序，其最坏情况下的时间复杂度为O(n log n)**，其中 n 是待排序元素的数量。堆排序不是稳定排序，但是原地排序（只需要常数级别的额外空间）**。堆排序的基本思想是将待排序的序列构造成一个最大堆或最小堆，这样就可以方便地取出最大值或最小值，然后将其与末尾元素交换，最后对剩下的 n-1 个元素重新调整成堆，重复这个过程直到所有元素都被排序。

​ 在堆排序中，我们通常使用最大堆（大顶堆），即每个父节点的值都大于或等于其子节点的值。最小堆（小顶堆）则是每个父节点的值都小于或等于其子节点的值。

代码

这里假设堆数组元素下标从0开始

#include <iostream>
#include <vector>
//这里假设堆数组元素下标从0开始
void heapify(std::vector<int>& arr, int n, int i) {//下滤操作 percolate down
    int largest = i; // Initialize largest as root
    int left = 2 * i+1; // 左子节点下标
    int right = 2 * i +2; // 右子节点下标

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// 实现堆排序
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 建堆
    for (int i = n / 2 - 1; i >= 0; i--)//（i=n/2-1）是因为堆数组的元素下标从零开始
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        std::swap(arr[0], arr[i]);

        // Call max heapify on the reduced heap
        heapify(arr, i, 0);//注意下滤操作的数组大小为i
    }
}

// Utility function to print an array
void printArray(const std::vector<int>& arr) {
    for (int i : arr)
        std::cout << i << " ";
    std::cout << "\n";
}

// Driver code
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);
    std::cout << "Sorted array is \n";
    printArray(arr);
}

一道作业题

题目：

指出堆排序如何处理输入数据 142，543,123,65,453,879,572,434,111,242,811,102。（手写过程）