กองเรียงใน C #

Heap Sort เป็นอัลกอริธึมการเรียงลำดับที่ใช้โครงสร้างข้อมูลฮีป ทุกครั้งที่องค์ประกอบรากของฮีปคือองค์ประกอบที่ใหญ่ที่สุดจะถูกลบออกและเก็บไว้ในอาร์เรย์ มันถูกแทนที่ด้วยองค์ประกอบลีฟด้านขวาสุด จากนั้นฮีปจะถูกสร้างขึ้นใหม่ สิ่งนี้จะเสร็จสิ้นจนกว่าจะไม่มีองค์ประกอบเหลืออยู่ในฮีปและจัดเรียงอาร์เรย์

โปรแกรมที่แสดงการเรียงลำดับฮีปใน 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 loop และเรียกใช้ฟังก์ชัน 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] + " ");
}