using System;

public class Program

{

    //http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

    //http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

    //http://practice.geeksforgeeks.org/problems/kth-smallest-element/0

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int[] array = {7, 10, 4, 3, 20, 15};

        int k  = 3;

        MinHeap(array); 

        int heapSize = array.Length;

        for(int i = 0; i < k - 1; i++, heapSize--)

        {

            ExtractMin(array,  heapSize);

        }

        Console.WriteLine(GetMin(array));

    }

    static int GetMin(int[] array)

    {

        return array[0];

    }

    static int ExtractMin(int[] heap, int heapSize)

    {

         if (heapSize == 0)

            return int.MaxValue;

        // Store the minimum vakue.

        int root = heap[0];

        // If there are more than 1 items, move the last item to root

        // and call heapify.

        if (heapSize > 1)

        {

            heap[0] = heap[heapSize-1];

            MinHeapify(heap, 0, heapSize);

        }

        return heap[0];

    }

    static void MinHeap(int[] ar)

    {

        int i = (ar.Length - 1)/2; 

        while(i >= 0)

        {

            MinHeapify(ar, i, ar.Length);           

            i--;

        }           

    }

    static void MinHeapify(int[] array, int i, int heapSize)

    {

        int l = 2*i + 1;

        int r = 2*i + 2;

        int smallest = i;

        if (l < heapSize && array[l] < array[smallest])

        {

            smallest = l;

        }

        if (r < heapSize && array[r] < array[smallest])

        {

            smallest = r;

        }

        if (smallest != i)

        {

            Swap(i, smallest, array);

            MinHeapify(array, i, heapSize);

        }

    }

    static void MaxHeapify(int[] heap, int k, int ix)

    {

        int l = 2*ix + 1;

        int r = 2*ix + 2;

        Console.WriteLine("{0} {1}", l, r);

        int largest = ix;

        if (l < heap.Length && heap[l] > heap[ix])

        {

            largest = l;

​

        }

        if (r < heap.Length && heap[r] > heap[largest])

        {

            largest = r;

        }

        Console.WriteLine("largest: {0}", largest);

        if (largest != ix)

        {

            Swap(ix, largest, heap);

            MaxHeapify(heap, k, largest); 

        }

    }

    static void Swap(int i, int j, int[] arr)

    {

        if (i==j || arr[i] == arr[j]) return;

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

}