<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:
    void pull_up(vector<int> &heap, int n){
        if(heap.size() == 1 || n==0) return;
        int parent = (n-1)/2;
        if(heap[n] > heap[parent]){
            swap(heap[parent], heap[n]);
            pull_up(heap, parent);
        }
        
    }
    
    void push_down(vector<int> &heap, int n){
        int child1 = 2*n+1;
        int child2 = 2*n+2; 
        if(child1 >= heap.size() && child2>=heap.size()) return;
        if(child2 >= heap.size()){
            if(heap[n] < heap[child1]){
                swap(heap[n], heap[child1]);
                push_down(heap, child1);
            }
            return;
        }
        int child = heap[child1] < heap[child2] ? child2 : child1;
        if(heap[n] < heap[child]){
            swap(heap[n], heap[child]);
            push_down(heap, child);
        }
        
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap;
        for(auto i : nums){
            heap.push_back(i);
            pull_up(heap, heap.size()-1);
        }
        
        for(auto j : heap){
            cout<<j<<" ";
        }
        cout<<endl;
        
        for(int i = 1 ; i<k ; i++){
            heap[0] = heap.back();
            heap.pop_back();
            push_down(heap, 0);
        }
        return heap[0];
        
    }
};
63300