C ++程序使用堆排序算法对10个元素的数组进行排序

堆排序基于二进制堆数据结构。在二进制堆中，在最大堆的情况下，父节点的子节点小于或等于它，在最小堆的情况下，父节点的子节点大于或等于它。

解释堆排序中所有步骤的示例如下。

排序前具有10个元素的原始数组为-

该数组使用max-heapify内置到二进制最大堆中。表示为数组的最大堆如下。

将提取最大堆的根元素，并将其放在数组的末尾。然后调用max heapify将其余元素转换为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]<<" ";