堆排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 堆排序演算法
  2. 堆排序示例
  3. 堆排序演算法的實現
  4. 堆排序演算法的複雜度
堆排序

堆排序是一種基於比較的排序演算法。它的名字來源於演算法中使用的堆資料結構。堆是一種基於二叉樹的特殊資料結構。它具有以下兩個特性。

  • 它是一棵完整的二叉樹,除了最後一個層外,所有層都被填滿。最後一層可能會被部分填滿,但所有的節點都儘可能的向左。
  • 所有的父節點都比它們的兩個子節點小/大。如果它們較小,堆稱為最小堆,如果較大,則堆稱為最大堆。對於給定的索引 i,父節點由 (i-1)/2 給出,左子節點由 (2*i+1) 給出,右子節點由 (2*i+2) 給出。

堆排序的工作方式與選擇排序很相似。它使用最大堆從陣列中選擇最大的元素,並將其放在陣列後面的位置。它利用一個叫做 heapify() 的過程來建立堆。

堆

堆排序演算法

假設我們有一個包含 n 元素的未排序陣列 A[]

HeapSort()

  • 用陣列 A 中的元素建立一個最大堆。
  • 對於從 A 中最後一個元素開始的每一個元素,執行以下操作。
  • 根元素 A[0] 將包含最大元素,將其與這個元素交換。
  • 將堆的大小減少一個,並 Heapify() 去掉最後一個元素後的最大堆。

Heapify()

  • 用當前元素的索引初始化 parent 索引。
  • 計算 leftChild2*i+1rightChild2*i+2
  • 如果 leftChild 處的元素大於 parent 索引處的值,則將 parent 索引設定為 leftChild
  • 如果 rightChild 處的元素大於 parent 索引處的值,則設定 parent 索引為 rightChild
  • 如果在上兩步中,parent 索引的值發生了變化,那麼將 parent 與當前元素交換,並遞迴 heapify parent 索引子樹。否則,堆屬性已經滿足。

堆排序示例

假設我們有陣列。(5, 3, 4, 2, 1, 6). 我們將使用堆排序演算法對其進行排序。

建立堆後,我們得到的陣列為:(6 3 5 2 1 4)(6 3 5 2 1 4)

  • 第一次迭代
Swap(A[5],A[0]) 4 3 5 2 1 6
Heapify() 5 3 4 2 1 6
  • 第二次迭代
Swap(A[4],A[0]) 1 3 4 2 5 6
Heapify() 4 3 1 2 5 6
  • 第三次迭代
Swap(A[3],A[0]) 2 3 1 4 5 6
Heapify() 3 2 1 4 5 6
  • 第四次迭代
Swap(A[2],A[0]) 1 2 3 4 5 6
Heapify() 2 1 3 4 5 6
  • 第五次迭代
Swap(A[1],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6
  • 第六次迭代
Swap(A[0],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6

我們得到的排序陣列為 :(1,2,3,4,5,6)

堆排序演算法的實現

#include<bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
    int parent = i;
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;

    if (leftChild < n && arr[leftChild] > arr[parent])
        parent = leftChild;

    if (rightChild < n && arr[rightChild] > arr[parent])
        parent = rightChild;

    if (parent != i) {
        swap(arr[i], arr[parent]);
        heapify(arr, n, parent);
    }
}

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 n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    heapSort(arr, n); // Sort elements in ascending order
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

堆排序演算法的複雜度

時間複雜度

  • 平均情況

具有 n 元素的完整二叉樹的高度為最大 logn。因此,當一個元素從根到葉移動時,heapify() 函式可以有最大的 logn 比較。構建堆函式對 n/2 元素進行呼叫,使得第一階段的總時間複雜度 n/2*lognT(n)=nlogn

HeapSort() 對每個元素都取 logn 最差時間,n 元素使其時間複雜度也為 nlogn。將建立堆和堆排序的時間複雜度相加,得到的複雜度為 nlogn。因此,總的時間複雜度是 [Big Theta]:O(nlogn)

  • 最壞情況

最壞情況下的時間複雜度為 [Big O]:O(nlogn)

  • 最佳情況

最佳情況下的時間複雜度是 [Big Omega]:O(nlogn)。它與最壞情況下的時間複雜度相同。

空間複雜度

堆排序演算法的空間複雜度為 O(n),因為除了臨時變數外,不需要額外的記憶體。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Sort Algorithm