堆排序
堆排序是一種基於比較的排序演算法。它的名字來源於演算法中使用的堆資料結構。堆是一種基於二叉樹的特殊資料結構。它具有以下兩個特性。
- 它是一棵完整的二叉樹,除了最後一個層外,所有層都被填滿。最後一層可能會被部分填滿,但所有的節點都儘可能的向左。
- 所有的父節點都比它們的兩個子節點小/大。如果它們較小,堆稱為最小堆,如果較大,則堆稱為最大堆。對於給定的索引
i
,父節點由(i-1)/2
給出,左子節點由(2*i+1)
給出,右子節點由(2*i+2)
給出。
堆排序的工作方式與選擇排序很相似。它使用最大堆從陣列中選擇最大的元素,並將其放在陣列後面的位置。它利用一個叫做 heapify()
的過程來建立堆。
堆排序演算法
假設我們有一個包含 n
元素的未排序陣列 A[]
。
HeapSort()
-
用陣列
A
中的元素建立一個最大堆。 -
對於從
A
中最後一個元素開始的每一個元素,執行以下操作。 -
根元素
A[0]
將包含最大元素,將其與這個元素交換。 -
將堆的大小減少一個,並
Heapify()
去掉最後一個元素後的最大堆。
Heapify()
-
用當前元素的索引初始化
parent
索引。 -
計算
leftChild
為2*i+1
,rightChild
為2*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*logn
或 T(n)=nlogn
。
HeapSort()
對每個元素都取 logn
最差時間,n
元素使其時間複雜度也為 nlogn
。將建立堆和堆排序的時間複雜度相加,得到的複雜度為 nlogn
。因此,總的時間複雜度是 [Big Theta]:O(nlogn)
。
- 最壞情況
最壞情況下的時間複雜度為 [Big O]:O(nlogn)
。
- 最佳情況
最佳情況下的時間複雜度是 [Big Omega]:O(nlogn)
。它與最壞情況下的時間複雜度相同。
空間複雜度
堆排序演算法的空間複雜度為 O(n)
,因為除了臨時變數外,不需要額外的記憶體。
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