数据结构
网络
关系数据库管理系统 (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 次浏览
广告