using System;

using C5;

​

public class Program

{

    //Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

    //Input: [3,2,1,5,6,4] and k = 2

    //Output: 5

    //You may assume k is always valid, 1 ≤ k ≤ array's length.

    public static int FindKthLargest(int[] nums, int k) {

        int n = nums.Length;

        IntervalHeap<int> heap = new IntervalHeap<int>();

        //check which is smaller: k or n-k+1

        if (k < n-k+1) {

            //get Kth largest element

            for (var i = 0; i < n; i++){

                if (heap.Count < k){

                    heap.Add(nums[i]);

                }

                else {

                    if (nums[i] > heap.FindMin()){

                        heap.DeleteMin();

                        heap.Add(nums[i]);

                    }

                }

            }

            return heap.FindMin();

        }

        else { //get n-k+1 smallest element - equivalent to Kth largest

            for (var i = 0; i < n; i++){

                if (heap.Count < n-k+1){

                    heap.Add(nums[i]);

                }

                else {

                    if (nums[i] < heap.FindMax()){

                        heap.DeleteMax();

                        heap.Add(nums[i]);

                    }

                }

            }

            return heap.FindMax();

        }

    }

​

    public static void Main()

    {

        //Input: [3,2,1,5,6,4] and k = 2

        var nums = new int[6]{3,2,1,5,6,4};

        var k = 2;

        Console.WriteLine(FindKthLargest(nums, k));

​

        k = 5;

        Console.WriteLine(FindKthLargest(nums, k));

    }

}