堆在C#中排序
堆排序是一种利用堆数据结构的排序算法。每次堆的根元素（即最大的元素）被删除并存储在数组中。将其替换为最右边的leaf元素，然后重新建立堆。完成此操作，直到堆中不再有其他元素并且对数组进行排序为止。
给出了一个用C#演示堆排序的程序，如下所示。
示例
using System;
namespace HeapSortDemo {
public class example {
static void heapSort(int[] arr, int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void Main() {
int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
heapSort(arr, 10);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}输出结果
上面程序的输出如下。
Heap Sort Initial array is: 55 25 89 34 12 19 78 95 1 100 Sorted Array is: 1 12 19 25 34 55 78 89 95 100
现在，让我们了解以上程序。
该函数main()包含数组arr。它打印初始数组，然后调用heapSort()将对数组进行排序的函数。在下面的代码片段中可以看到。
int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
heapSort(arr, 10);该函数heapSort()首先将给定的元素转换为堆。这是通过使用for循环并heapify()为堆的所有非叶元素调用函数来完成的。在下面的代码片段中可以看到。
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
创建堆之后，将使用for循环删除堆的根元素，即最大的元素。将其替换为最右边的leaf元素，然后heapify()再次调用以重新建立堆。在下面的代码片段中可以看到。
for (int i = n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}该函数heapify()通过按需排列元素来创建堆结构。此过程从索引i处的元素开始，因为它被认为是heapify()函数的根元素。在下面的代码片段中可以看到。
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}最后，排序后的数组将显示在main()函数中。在下面的代码片段中可以看到。
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}