using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        PriorityQueue<int, int> maxHeap = 

            new PriorityQueue<int, int>(Comparer<int>.Create((a,b) => b - a));

​

        maxHeap.Enqueue(8, 8);

        maxHeap.Enqueue(9, 9);

        maxHeap.Enqueue(10, 10);

        maxHeap.Enqueue(1, 1);

        maxHeap.Enqueue(11, 11);

        while(maxHeap.Count > 0) {

            var v = maxHeap.Dequeue();

            Console.WriteLine($"{v}");

        }

        Console.WriteLine("Hello World");

    }

}

​

public class Solution2 {

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

        var k_ind = nums.Length - k;

​

        return QuickSelect(nums, 0, nums.Length - 1, k_ind);

    }

​

    private int QuickSelect(int[] nums, int low, int high, int k){

        var r = new Random();

        var pi = r.Next(low, high + 1);

        var pivot = nums[pi];

        int i = low;

        int left = low - 1; // pointer to the last element which is smaller than the pivot

        int right = high + 1; // pointer to the first element which is greater than the privot

​

        while(i < right){

            if(nums[i] < pivot){

                Swap(nums, i++, ++left);

            }else if(nums[i] > pivot){

                Swap(nums, i, --right);

            }else{

                i++;

            }

        }

​

        var start = left + 1;

        var end = right - 1;

​

        if(k >= start && k <= end)

            return nums[k];

        if(k < start)

            return QuickSelect(nums, low, start - 1, k);

        return QuickSelect(nums, end+1, high, k);

    }

​

    private void Swap(int[] nums, int i, int j){

        var temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

public class Solution3 {

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

        var priorityQ = new PriorityQueue<int, int>();

        foreach (var n in nums){

            priorityQ.Enqueue(n, n);

            if (priorityQ.Count > k){

                priorityQ.Dequeue();

            }

        }

        return priorityQ.Peek();

    }

}

​

class Solution4 {

    public int findKthLargest(int[] nums, int k) {

        List<int> list = new List<int>();

        foreach (int num in nums) {

            list.Add(num);

        }

        return quickSelect(list, k);

    }

    public int quickSelect(List<int> nums, int k) {

        int pivotIndex = new Random().Next()% nums.Count;

        int pivot = nums[pivotIndex];

        List<int> left = new List<int>();

        List<int> mid = new List<int>();

        List<int> right = new List<int>();

        foreach (int num in nums) {

            if (num > pivot) {

                left.Add(num);

            } else if (num < pivot) {

                right.Add(num);

            } else {

                mid.Add(num);

            }

        }

        if (k <= left.Count) {

            return quickSelect(left, k);

        }

        if (left.Count + mid.Count < k) {

            return quickSelect(right, k - left.Count - mid.Count);

        }

        return pivot;

    }

}

​

class Solution5 {

    public int findKthLargest(int[] nums, int k) {

        int minValue = int.MaxValue;

        int maxValue = int.MinValue;

        foreach (int num in nums) {

            minValue = Math.Min(minValue, num);

            maxValue = Math.Max(maxValue, num);

        }

        int[] count = new int[maxValue - minValue + 1];

        foreach (int num in nums) {

            count[num - minValue]++;

        }

        int remain = k;

        for (int num = count.Length - 1; num >= 0; num--) {

            remain -= count[num];

            if (remain <= 0) {

                return num + minValue;

            }

        }

        return -1;

    }

}

/*

class Solution:

    def findKthLargest(self, nums: List[int], k: int) -> int:

        left = 0

        right = len(nums)

        while right - left > 100:

            m = left + (right - left) // 2

            pivot = nums[m]

            lt = left  # pointer to put next element less than (lt) pivot

            le = left  # pointer to put next element less or equal (le) pivot

            for i in range(left, right):

                if nums[i] > pivot:

                    nums[i], nums[le] = nums[le], nums[i]

                    nums[lt], nums[le] = nums[le], nums[lt]

                    le += 1

                    lt += 1

                elif nums[i] == pivot:

                    nums[i], nums[le] = nums[le], nums[i]

                    le += 1

            # [left,  lt) : < pivot

            # [lt,     e) : = pivot

            # [le, right) : > pivot

            lt_cnt = lt - left

            le_cnt = le - left

            if k <= lt_cnt:

                left = left

                right = left + lt_cnt

                k = k

            elif k <= le_cnt:

                return pivot

            else:

                left = left + le_cnt

                right = right

                k = k - le_cnt

        # have a small array left, just sort it, it will work faster

        rest = [nums[i] for i in range(left, right)]

        rest.sort(reverse=True)

        return rest[k-1]

        */

​

// https://leetcode.com/explore/learn/card/heap/