您的位置:

堆排序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 < n && arr[l] > arr[largest]) 
        largest = l; 

    // 如果右子节点比父节点大 
    if (r < n && arr[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 < n && arr[l] > arr[largest]) 
        largest = l; 

    // 如果右子节点比父节点大 
    if (r < n && arr[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