C# 힙 정렬

힙정렬은 트리 구조에서 이진트리를 이용해

최대 힙을 구해서 오른쪽 배열부터 최대값을 넣어서 인덱스에 저장된 최대값을 빼버리고

다시 이진트리에 최대힙을 구해서 넣고 반복해서 정렬하는 알고리즘 구조이다.

using System;
using System.Collections.Generic;

namespace 힙_정렬
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<int> heap = new List<int>();

            int[] heapsort = new int[n];

            string[] arr = Console.ReadLine().Split();
            for (int i = 0; i < n; i++)
            {
                heap.Add(int.Parse(arr[i]));
            }

            HeapSortAlgorithm();

            foreach (int a in heap)
            {
                Console.Write($"{a} ");
            }

            Console.WriteLine();

            for (int i = heap.Count - 1; i >= 0; i--)
            {
                heapsort[i] = heap[0];
                heap[0] = heap[i];
                heap.RemoveAt(i);
                MaxHeapify(0);
            }

            foreach (int a in heapsort)
            {
                Console.Write($"{a} ");
            }

            void HeapSortAlgorithm()
            {
                int heapSize = heap.Count;
                for (int i = heapSize / 2 - 1; i >= 0; i--)
                {
                    MaxHeapify(i);
                }
            }

            void MaxHeapify(int parent)
            {
                int leftChild = 2 * parent + 1;
                int rightChild = 2 * parent + 2;
                int largest = parent;

                if (leftChild < heap.Count && heap[leftChild] > heap[largest])
                    largest = leftChild;

                if (rightChild < heap.Count && heap[rightChild] > heap[largest])
                    largest = rightChild;

                if (largest != parent)
                {
                    Swap(parent, largest);
                    MaxHeapify(largest);
                }
            }

            void Swap(int parent, int child)
            {
                int temp;
                temp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = temp;
            }
        }
    }
}

이번에는 다른 정렬 알고리즘보다 오래 걸린거 같다.

제대로 작동이 되지만은 솔직히 잘 짠건지는 잘모르겠다..