<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k<sup>th</sup></code> <em>largest element in the array</em>.</p>

<p>Note that it is the <code>k<sup>th</sup></code> largest element in the sorted order, not the <code>k<sup>th</sup></code> distinct element.</p>

<p>Can you solve it without sorting?</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,1,5,6,4], k = 2
<strong>Output:</strong> 5
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,3,1,2,4,5,5,6], k = 4
<strong>Output:</strong> 4
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    class MaxHeap
    {
        public:
        int heapsize;
        int* arr;
        int capacity;
        
         MaxHeap(int size)
        {
            capacity = size;
            heapsize = 0;
            arr = new int[capacity];
        }
        int parent(int i)
        {
            return (i-1)/2;
        }
        int left(int i)
        {
            return (2*i)+1;
        }
        int right(int i)
        {
            return (2*i)+2;
        }
        void insertKey(int val)
        {
            if(heapsize<capacity)
            {
                arr[heapsize] = val;
                heapsize++;
                int i = heapsize-1;
                while(i>0 && arr[parent(i)]<arr[i])
                {
                    swap(arr[parent(i)], arr[i]);
                    i = parent(i);
                }
            }
        }

        int removeKey()
        {
            int temp = arr[0];
            arr[0] = arr[heapsize-1];
            heapsize--;
            maxHeapify(0);
            return temp;
        }

        void maxHeapify(int i)
        {
            int l = left(i);
            int r = right(i);
            int maxl = i;
            if(l<heapsize && arr[l]>arr[maxl])
            {
                maxl = l;
            }
            if(r<heapsize && arr[r]>arr[maxl])
            {
                maxl = r;
            }
            if(arr[maxl]>arr[i])
            {
                swap(arr[maxl],arr[i]);
                maxHeapify(maxl);
            }
        }

    };
    int findKthLargest(vector<int>& nums, int k) {
       MaxHeap* maxheap = new MaxHeap(100000);
       for(int i = 0;i<nums.size();i++)
       {
            maxheap->insertKey(nums[i]);
       }
       int t;
        // for(int i =0;i<maxheap->heapsize;i++)
        // {
        //     cout<<maxheap->arr[i]<<" ";
        // }
        // cout<<endl;
       for(int i =0;i<k;i++)
       {
            t = maxheap->removeKey();
       }
       return t;
    }
};
62200