<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 MinHeap{
    public:
        int heap[INT_MAX];
        int size;

        MinHeap(){
            heap[0] = -1;
            size = 0;
        }

        int top(){
            return heap[1];
        }

        void insert(int val){
            heap[++size] = val;
            int ind = size;

            while(ind > 1){
                int parent = ind / 2;
                if(heap[parent] > heap[ind]){
                    swap(heap[parent], heap[ind]);
                    ind = parent;
                } else
                    break;
            }
        }

        void pop(){
            if(size == 0) return;

            heap[1] = heap[size];
            size--;
            int i = 1, smallest = 1;
            while(i < size){
                int left = 2 * i;
                int right = 2 * i + 1;

                if(left <= size && heap[i] > heap[left])
                    smallest = left;
                if(right <= size && heap[smallest] > heap[right])
                    smallest = right;

                if(smallest != i){
                    swap(heap[i], heap[smallest]);
                    i = smallest;
                } else
                    break;
            }
        }

        void print(){
            for(int i = 1; i <= size; i++){
                cout << heap[i] << " ";
            }
        }
};
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        MinHeap *heap = new MinHeap();

        // insert the 1st k elements into the min heap
        for(int i = 0; i < k; i++){
            heap->insert(nums[i]);
        }

        for(int i = k; i < nums.size(); i++){
            // if top is less than the current element then pop from heap and insert the element
            if(heap->top() < nums[i]){
                heap->pop();
                heap->insert(nums[i]);
            }
        }
        heap->print();

        return heap->top();
    }
};
59700