堆排序 - 堆排序是一种基于比较的算法，它使用二叉树数据结构按升序或降序对数字列表进行排序。它通过堆排序创建一个堆数据结构，其中根是最小元素，然后删除根，再次排序在根位置给出列表中第二小的数字。
最小堆 - 最小堆是一种数据结构，其中父节点始终小于子节点，因此根节点是所有元素中最小的元素。
问题陈述给定一个整数数组。使用最小堆按降序对它们进行排序。
示例 1input: [2, 5, 1, 7, 0]
output: [7, 5, 2, 1, 0]
示例 2input: [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 minheapend procedure
示例：c++ 实现在下面的程序中，我们使用最小堆对数组进行排序，然后反转顺序以获得结果。
#include <bits/stdc++.h>using namespace std;// function to heap sort in decreasing order using min heapvoid 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 ifend procedureprocedure 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 ivoid 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 来恢复最小堆的属性，而是使用传统的 hep 排序算法来创建 amin堆和排序元素的顺序递增，并进一步反转以获得所需的输出。
伪代码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 ifend 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)，每种方法的空间复杂度各不相同。
以上就是使用最小堆进行降序的堆排序的详细内容。