堆排序

1. 堆排序演算法
2. 堆排序示例
3. 堆排序演算法的實現
4. 堆排序演算法的複雜度

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

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

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

堆排序演算法

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

HeapSort()

Heapify()

堆排序示例

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

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

• 第一次迭代

• 第二次迭代

• 第三次迭代

• 第四次迭代

• 第五次迭代

• 第六次迭代

我們得到的排序陣列為 ：(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*logn 或 T(n)=nlogn。

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

• 最壞情況

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

• 最佳情況

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

空間複雜度

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