堆排序C++详解

一、堆排序概述

堆排序是一种基于堆的排序算法，它的时间复杂度为O(nlogn)。它是选择排序的一种改进，在原选择排序的基础上，将未排序元素中最大值与末尾位置交换，可获得从小到大排列的有序数组。

二、堆排序实现原理

堆是一种特殊的树型数据结构，满足任意节点都大于等于（小于等于）左右子节点。堆排序的实现基于堆的特性，在构建堆时，它必须满足两个原则：结构性（完全二叉树）和堆序性（节点都大于等于（小于等于）左右子节点）。在这个堆的基础上，我们可以将堆顶元素（最大值或最小值）与末尾元素交换，然后将剩余未排序的元素重新构建堆。如此反复执行，直到所有元素都排好序。

三、堆排序实现步骤

1.建立堆

通常使用二叉堆来实现，分为最大堆和最小堆。首先，从最后一个非叶子节点开始，依次将每个节点调整为根节点向下的最大（最小）节点。这一过程叫做“堆的调整”。

void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // 父节点（根节点） 
    int l = 2*i + 1; // 左子节点 
    int r = 2*i + 2; // 右子节点 

    // 如果左子节点比父节点大 
    if (l  arr[largest]) 
        largest = l; 

    // 如果右子节点比父节点大 
    if (r  arr[largest]) 
        largest = r; 

    // 如果最大的节点不是父节点 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 

        // 递归调用堆的构建 
        heapify(arr, n, largest); 
    } 
} 

2.交换堆顶元素和末尾元素

我们将堆顶元素和末尾元素交换，并重新调整剩余元素的堆，以维持堆的特性。

void heapSort(int arr[], int n) 
{ 
    // 构建堆（最大堆） 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

    // 一个一个的取出堆顶元素 
    for (int i=n-1; i>=0; i--) 
    { 
        // 将堆顶元素和当前未排序末尾元素交换 
        swap(arr[0], arr[i]); 

        // 调整堆 
        heapify(arr, i, 0); 
    } 
} 

四、堆的时间复杂度

堆排序的时间复杂度是O(nlogn)，其中建堆的时间复杂度为O(n)。

五、堆排序应用场景

堆排序的应用较广泛，例如Top K问题、求中位数、优先级队列等。

六、堆排序的优缺点

优点：

1.时间复杂度较低，不会因数据数量增加而增加太多的时间。

2.堆排序是一种原地排序算法，不需要额外的存储空间。

3.堆排序是一种稳定的排序算法。

缺点：

1.对于小规模数据排序，堆排序的时间复杂度并不比快速排序、归并排序好。

2.堆排序算法常数较大，不适合于数据量较小的情况。

七、代码实现

#include  
using namespace std; 

// 调整堆 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // 父节点（根节点） 
    int l = 2*i + 1; // 左子节点 
    int r = 2*i + 2; // 右子节点 

    // 如果左子节点比父节点大 
    if (l  arr[largest]) 
        largest = l; 

    // 如果右子节点比父节点大 
    if (r  arr[largest]) 
        largest = r; 

    // 如果最大的节点不是父节点 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 

        // 递归调用堆的构建 
        heapify(arr, n, largest); 
    } 
} 

// 堆排序 
void heapSort(int arr[], int n) 
{ 
    // 构建堆（最大堆） 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

    // 一个一个的取出堆顶元素 
    for (int i=n-1; i>=0; i--) 
    { 
        // 将堆顶元素和当前未排序末尾元素交换 
        swap(arr[0], arr[i]); 

        // 调整堆 
        heapify(arr, i, 0); 
    } 
} 

int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    heapSort(arr, n); 

    cout << "排序后的数组：\n"; 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << endl; 
}