資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用最小堆進行降序堆排序
堆排序 - 堆排序是一種基於比較的演算法，它使用二叉樹資料結構將數字列表按升序或降序排序。它透過建立堆資料結構來進行堆排序，其中根節點是最小元素，然後移除根節點並再次排序，使列表中第二小的數字位於根節點位置。
最小堆 - 最小堆是一種資料結構，其中父節點始終小於子節點，因此根節點是所有元素中最小的元素。
問題陳述
給定一個整數陣列。使用最小堆將其按降序排序。
示例 1
Input: [2, 5, 1, 7, 0]
Output: [7, 5, 2, 1, 0]
示例 2
Input: [55, 1, 23, 10, 1]
Output: [55, 23, 10, 1, 1]
方法 1
為了使用最小堆進行降序堆排序，我們建立元素的最小堆，並一次提取一個元素，透過反轉順序得到降序陣列。
虛擬碼
procedure heapSort (arr[], n)
Initialize priority queue: minHeap
for i = 1 to n
add arr[i] to minHeap
i = n - 1
while minHeap is not empty
arr[i–] = top element of minHeap
Remove the top element of minHeap
end procedure
示例：C++ 實現
在下面的程式中，我們使用最小堆對陣列進行排序，然後反轉順序以獲得結果。
#include <bits/stdc++.h>
using namespace std;
// Function to heap sort in decreasing order using min heap
void heapSort(int arr[], int n){
// Creating min heap using a priority queue
priority_queue<int, vector<int>, greater<int> > minHeap;
// Inserting input array to min heap
for (int i = 0; i < n; i++){
minHeap.push(arr[i]);
}
// Iterating backwards in the input array, where each element is replaced by the smallest element extracted from min heap
int i = n - 1;
while (!minHeap.empty()){
arr[i--] = minHeap.top();
minHeap.pop();
}
}
int main(){
int arr[6] = {5, 2, 9, 1, 5, 6};
int n = 6;
heapSort(arr, n);
cout << "Sorted array : ";
for (int i = 0; i < n; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
輸出
Sorted array : 9 6 5 5 2 1
時間複雜度 - O(nlogn)
空間複雜度 - O(n)
方法 2
解決這個問題的另一種方法是從最後一個非葉子根節點開始，向後構建最小堆。然後，我們可以透過將根節點與最後一個葉子節點交換，然後恢復最小堆屬性來對陣列進行排序。
虛擬碼
procedure heapify (arr[], n , i)
smallest = i
l = 2i + 1
r = 2i + 2
if l < n and arr[l] < arr[smallest]
smallest = l
end if
if r < n and arr[r] < arr[samllest]
smallest = r
end if
if smallest is not i
swap arr[i] to arr[smallest]
heapify (arr, n, smallest)
end if
end procedure
procedure heapSort (arr[], n)
for i = n/2 - 1 to 0
heapify(arr, n, i)
for i = n-1 to 0
swap arr[0] to arr[i]
heapify (arr, i, 0)
end procedure
示例：C++ 實現
在下面的程式中，我們使用 `heapify()` 函式來恢復以索引 i 為根的子樹的最小堆屬性，`heapSort()` 函式則以反序構建最小堆。
#include <bits/stdc++.h>
using namespace std;
// Restores the min heap property of subtree rooted at index i
void heapify(int arr[], int n, int i){
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] < arr[smallest]){
smallest = l;
}
if (r < n && arr[r] < arr[smallest]){
smallest = r;
}
if (smallest != i){
swap(arr[i], arr[smallest]);
heapify(arr, n, smallest);
}
}
void heapSort(int arr[], int n){
// Build the min heap in reverse order
for (int i = n / 2 - 1; i >= 0; i--){
heapify(arr, n, i);
}
// Sort the array by repeatedly swapping the root node with the last leaf node
for (int i = n - 1; i >= 0; i--){
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main(){
int arr[6] = {5, 2, 9, 1, 5, 6};
int n = 6;
heapSort(arr, n);
cout << "Sorted array : ";
for (int i = 0; i < n; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
輸出
Sorted array : 9 6 5 5 2 1
使用前面使用 `heapSort()` 函式建立最小堆的方法，我們可以在此解決方案中使用相同的方法，但不是使用 `heapify` 來恢復最小堆的屬性，而是使用傳統的堆排序演算法來建立最小堆並按升序排序元素，然後反轉順序以獲得所需的輸出。
虛擬碼
procedure heapSort (arr[], n)
for i = n/2 - 1 to 0
parent = i
while parent *2+1 < n
child = parent*2+1
if child+1 < n and arr[child] >arr[child+1]
child = child + 1
end if
if arr[parent] > arr[child]
swap arr[parent] to arr[child]
parent = child
else
break
end if
for i = n-1 to 0
swap arr[0] to arr[i]
parent = 0
while parent*2+1 < i
child = parent*2+1
if child+1 < n and arr[child] >arr[child+1]
child = child + 1
end if
if arr[parent] > arr[child]
swap arr[parent] to arr[child]
parent = child
else
break
end if
end procedure
示例：C++ 實現
在下面的程式中，我們修改堆排序演算法以按降序對陣列進行排序。
#include <bits/stdc++.h>
using namespace std;
void heapSort(int arr[], int n){
// Building min heap in reverse order
for (int i = n / 2 - 1; i >= 0; i--) {
// Starting from last parent node, apply heapify operation
int parent = i;
while (parent * 2 + 1 < n) {
int child = parent * 2 + 1;
if (child + 1 < n && arr[child] > arr[child + 1]){
child++;
}
if (arr[parent] > arr[child]){
swap(arr[parent], arr[child]);
parent = child;
}
else{
break;
}
}
}
// Extarct elekemnhts form min heap in decreasing order
for (int i = n - 1; i > 0; i--){
swap(arr[0], arr[i]);
int parent = 0;
// Perform heapify operation at new root node
while (parent * 2 + 1 < i){
int child = parent * 2 + 1;
if (child + 1 < i && arr[child] > arr[child + 1]){
child++;
}
if (arr[parent] > arr[child]){
swap(arr[parent], arr[child]);
parent = child;
}
else {
break;
}
}
}
}
int main(){
int arr[6] = {5, 2, 9, 1, 5, 6};
int n = 6;
heapSort(arr, n);
cout << "Sorted array : ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
輸出
Sorted array : 9 6 5 5 2 1
結論
總之，為了使用最小堆進行降序堆排序，我們可以使用幾種方法，其中一些方法如上所述，時間複雜度為 O(nlogn)，每種方法的空間複雜度不同。
更新於：2023年7月25日
682 次瀏覽
廣告