public static void HeapSort(int[] input, bool maxHeap = false)
        {
            BuildHeap(input, maxHeap);
            int inputSize = input.Length;
            for (int i = input.Length-1; i>=1; i--)
            {
                int tmp = input[i];
                input[i] = input[0];
                input[0] = tmp;
                inputSize--;
                Heapify(input, inputSize, 0, maxHeap);
            }
        }



        public static void Heapify(int[] heap, int heapSize, int i, bool maxHeap = false)
        {
            if (maxHeap)
            {
                int l = 2 * i;
                int r = 2 *i + 1;
                int max = i;
                if (l < heapSize && heap[l] > heap[i])
                    max = l;
                if (r < heapSize && heap[r] > heap[max])
                    max = r;
                if (max != i)
                {
                    int tmp = heap[i];
                    heap[i] = heap[max];
                    heap[max] = tmp;
                    Heapify(heap, heapSize, max, maxHeap);
                }
            }
            else
            {
                int l = 2*i;
                int r = 2*i+1;
                int min = i;
                if (l < heapSize && heap[l] < heap[i])
                    min = l;
                if (r < heapSize && heap[r] < heap[min])
                    min = r;
                if (min != i)
                {
                    int tmp = heap[i];
                    heap[i] = heap[min];
                    heap[min] = tmp;
                    Heapify(heap, heapSize, min, maxHeap);
                }
            }
        }

        public static void BuildHeap(int[] list, bool maxHeap = false)
        {
            for (int i = list.Length/2; i >= 0; i--)
            {
                Heapify(list, list.Length, i, maxHeap);
            }
        }
    }