Sắp xếp đống trong C #

Heap Sort là một thuật toán sắp xếp sử dụng cấu trúc dữ liệu đống. Mỗi lần phần tử gốc của heap, tức là phần tử lớn nhất bị xóa và được lưu trữ trong một mảng. Nó được thay thế bằng phần tử lá ngoài cùng bên phải và sau đó heap được thiết lập lại. Điều này được thực hiện cho đến khi không còn phần tử nào nữa trong đống và mảng được sắp xếp.

Một chương trình thể hiện sắp xếp đống trong C # được đưa ra như sau.

Ví dụ

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] + " ");
         }
      }
   }
}

Đầu ra

Kết quả của chương trình trên như sau.

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

Bây giờ, chúng ta hãy hiểu chương trình trên.

Hàm main () chứa mảng arr. Nó in mảng ban đầu và sau đó gọi hàm heapSort () sẽ sắp xếp mảng. Điều này có thể được nhìn thấy trong đoạn mã sau.

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);

Đầu tiên, hàm heapSort () chuyển đổi các phần tử đã cho thành một heap. Điều này được thực hiện bằng cách sử dụng vòng lặp for và gọi hàm heapify () cho tất cả các phần tử không phải lá của heap. Điều này có thể được nhìn thấy trong đoạn mã sau.

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

Sau khi heap được tạo, vòng lặp for được sử dụng để xóa phần tử gốc của heap, tức là phần tử lớn nhất. Nó được thay thế bằng phần tử lá ngoài cùng bên phải và sau đó heapify () được gọi lại để thiết lập lại heap. Điều này có thể được nhìn thấy trong đoạn mã sau.

for (int i = n-1; i>=0; i--) {
   int temp = arr[0];
   arr[0] = arr[i];
   arr[i] = temp;
   heapify(arr, i, 0);
}

Hàm heapify () tạo cấu trúc heap bằng cách sắp xếp các phần tử theo yêu cầu. Quá trình này bắt đầu từ phần tử ở chỉ mục i vì đây được coi là phần tử gốc của hàm heapify (). Điều này có thể được nhìn thấy trong đoạn mã sau.

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);
}

Cuối cùng, mảng đã sắp xếp được hiển thị trong hàm main (). Điều này có thể được nhìn thấy trong đoạn mã sau.

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}