using System;

using System.Linq;

​

public class Program

{

    // Звено списка

    public class Node

    {

        public Node next;

        public int data;

    }

​

    // Односвязный список

    public class LinkedList

    {

        // Первое звено в цепи

        private Node _head = null;

        public LinkedList()

        {

        }

​

        public Node GetHead()

        {

            return _head;

        }

​

        // Инициализация списка с набором данных

        public LinkedList(int[] inputData)

        {

            foreach (int data in inputData)

            {

                AddLast(data);

            }

        }

​

        // Есть ли звенья в списке

        public bool HasNodes()

        {

            return _head != null;

        }

​

        // Вывод в консоль всех элементов списка (для наглядности)

        // плюс сообщение перед выводом списка (костыль для наглядности)

        public void PrintAllNodes(string inputText = null)

        {

            if (!HasNodes())

            {

                return;

            }

​

            if (!String.IsNullOrEmpty(inputText))

            {

                Console.WriteLine(inputText);

            }

​

            Node current = _head;

            while (current != null)

            {

                Console.Write(current.data + " ");

                current = current.next;

            }

​

            Console.WriteLine();

            if (!String.IsNullOrEmpty(inputText))

            {

                Console.WriteLine("-------------------");

            }

        }

​

        // Добавить элемент в конец списка по полученным данным

        public void AddLast(int data)

        {

            if (_head == null)

            {

                _head = new Node();

                _head.data = data;

                _head.next = null;

            }

            else

            {

                Node toAdd = new Node();

                toAdd.data = data;

                Node current = _head;

                while (current.next != null)

                {

                    current = current.next;

                }

​

                current.next = toAdd;

            }

        }

​

        // Добавить элемент в конце списка по даным из другого звена

        public void AddLast(Node node)

        {

            if (_head == null)

            {

                _head = new Node();

                _head.data = node.data;

                _head.next = null;

            }

            else

            {

                Node toAdd = new Node();

                toAdd.data = node.data;

                Node current = _head;

                while (current.next != null)

                {

                    current = current.next;

                }

​

                current.next = toAdd;

            }

        }

​

        // Удалить первый элемент в цепи (возвращает удаленный элемент по желанию)

        public Node RemoveHead()

        {

            if (!HasNodes())

            {

                return null;

            }

​

            var current = _head;

            if (current.next != null)

            {

                current = current.next;

            }

            else

            {

                current = null;

            }

​

            var headToReturn = _head;

            _head = current;

            return headToReturn;

        }

    }

​

    // Инициализация входных данных

    // Согласно условию, элементы внутри списков отсортированы

    public static LinkedList[] GetInitialList()

    {

        return new LinkedList[]

        {

            new LinkedList(new int[]{8, 9}),

            new LinkedList(new int[]{1, 2, 3}),

            new LinkedList(new int[]{4, 5, 6}),

            new LinkedList(new int[]{7, 10})

        };

    }

​

    // Запуск алгоритма пирамидальной сортировки

    private static void performHeapSort(LinkedList[] arr)

    {

        int n = arr.Length;

        // Построить пирамиду/кучу (heap) 

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

            rebuildHeap(arr, n, i);

        // Удаляем по одному элементу из пирамиды/кучи

        for (int i = n - 1; i >= 0; i--)

        {

            // Поменять местами первый и последний элементы

            LinkedList temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // call max on the reduced heap 

            rebuildHeap(arr, i, 0);

        }

    }

​

    // Перестройка массива для пирамидальной сортировки (сортировочное дерево)

    // Сравниваем элементы массива (являющиеся односвязными списками) по головным звеньям

    private static void rebuildHeap(LinkedList[] arr, int n, int i)

    {

        int largest = i; // Корень 

        int l = 2 * i + 1; // left = 2*i + 1 (левый потомок)

        int r = 2 * i + 2; // right = 2*i + 2 (правый потомок)

        // Если левый потомок больше родителя

        if (l < n && arr[l].GetHead().data > arr[largest].GetHead().data)

            largest = l;

        // Если правый потомок больше родителя 

        if (r < n && arr[r].GetHead().data > arr[largest].GetHead().data)

            largest = r;

        // Если largest не является корнем

        if (largest != i)

        {

            LinkedList swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

            // Рекурсивно перестраиваем массив

            rebuildHeap(arr, n, largest);

        }

    }

​

    // Вывод текущего состояния массива с входными данными (для наглядности)

    public static void PrintListArray(LinkedList[] listArray)

    {

        Console.WriteLine("List Array:");

        foreach (LinkedList list in listArray)

        {

            list.PrintAllNodes();

        }

​

        Console.WriteLine("----");

    }

​

    public static void Main()

    {

        var initialList = GetInitialList(); // Получаем входные данные

        var resultList = new LinkedList(); // Инициализация результирующего списка

        PrintListArray(initialList); // Вывод изначального состояния массива с входными данными

        // Цикл продолжается, пока есть элементы в массиве (и звенья в списках) с входными данными

        while (initialList.Length > 0)

        {

            performHeapSort(initialList); // Сортируем

            // Первое звено первого списка всегда будет самым наименьшим из всех элементов в совокупности;

            // Удаляем его из входных данных, добавляем в результирующий список и будем снова сортировать входные данные

            var newNode = initialList[0].RemoveHead(); 

            resultList.AddLast(newNode);

            PrintListArray(initialList);

            resultList.PrintAllNodes("Result list:");

            // Проверяем, остались ли звенья в списке, из которого удалили элемент,

            // Если нет - удаляем список из массива входных данных  

            if (!initialList[0].HasNodes())

            {

                initialList = initialList.Where((val, i) => i != 0).ToArray();

            }

        }

    }

}