堆排序 - 堆排序是一种基于比较的算法，它使用二叉树数据结构按升序或降序对数字列表进行排序。它通过堆排序创建一个堆数据结构，其中根是最小元素，然后删除根，再次排序在根位置给出列表中第二小的数字。
最小堆 - 最小堆是一种数据结构，其中父节点始终小于子节点，因此根节点是所有元素中最小的元素。
问题陈述
给定一个整数数组。使用最小堆按降序对它们进行排序。
示例 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
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 minHeap;
// Inserting input array to min heap
for (int i = 0; i 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 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
