C ++程序使用堆排序算法对10个元素的数组进行排序
堆排序基于二进制堆数据结构。在二进制堆中，在最大堆的情况下，父节点的子节点小于或等于它，在最小堆的情况下，父节点的子节点大于或等于它。
解释堆排序中所有步骤的示例如下。
排序前具有10个元素的原始数组为-
该数组使用max-heapify内置到二进制最大堆中。表示为数组的最大堆如下。
将提取最大堆的根元素，并将其放在数组的末尾。然后调用maxheapify将其余元素转换为max堆。这样做直到最终获得排序的数组，如下所示-
下面给出了使用堆排序算法对10个元素的数组进行排序的程序。
示例
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int temp;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
int n = 10;
i nt i;
cout<<"Given array is: "<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
}输出结果
Given array is: 20 7 1 54 10 15 90 23 77 25 Sorted array is: 1 7 10 15 20 23 25 54 77 90
在以上程序中，该函数heapify()用于将元素转换为堆。该函数是递归函数，它从被调用的元素（在本例中为i）开始创建最大堆。证明这一点的代码片段如下。
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}该函数heapSort()使用堆排序排序数组元素的。它从非叶节点开始，并heapify()在每个非叶节点上调用。这会将数组转换为二进制最大堆。这显示如下-
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
之后，该函数heapSort()在for循环的每次迭代中获取根元素，并将其放在数组的末尾。然后heapify()调用，以确保其余元素为最大堆。最终，使用此方法从最大堆中取出所有元素，并获得排序的数组。如下所示。
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}在函数中main()，首先显示数组。然后，heapSort()调用该函数对数组进行排序。这是由以下代码片段给出的。
cout<<"Given array is: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n);
最后，显示排序后的数组。如下所示。
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";