堆排序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; 
}