<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 MaxHeap
{
    private:
    vector<int> T;
    int sz;

    int MaxIndex(int a, int b, int c)
    {
        if (T[a]>=T[b] && T[a]>=T[c]) { return a ;}
        else if (T[b]>=T[a] && T[b]>=T[c]) { return b ;}
        return c;
    }

    void swap(int i, int j)
    {
        int temp = T[i] ;
        T[i] = T[j] ;
        T[j] = temp;
        return ;
    }

    int parent(int i)
    {
        return (i-1)/2 ;
    }

    int left(int i) { return 2*i+1 ; }
    int right(int i) { return 2*i+2 ; }

    public:
    MaxHeap() : sz(0) {}
    MaxHeap(vector<int>& A)
    {
        T = A ;
        sz = T.size() ;
    }

    void insert(int p)
    {
        if (sz == T.size())
        {
            T.push_back(p) ;
        }
        else
        {
            T[sz] = p ; 
        }
        int i = sz;
        while( T[parent(i)]<T[i] && i>0)
        {
            swap(parent(i), i) ;
            i = parent(i) ;
        }
        sz++;
        return ;
    }

    void Heapify(int i)
    {
        if (left(i)>=sz && right(i)>=sz)
        {
            return ;
        }
        int c ;
        // Only right is out
        if (right(i)>=sz)
        {
            c = (T[left(i)]>T[i])?left(i):i ;
        }
        else
        {
            c = MaxIndex(left(i), right(i), i) ;
        }
        if (c==i)
        {
            return ;
        }
        swap(c, i) ;
        Heapify(c) ;
        return ;
    }

    void BuildHeap()
    {
        for (int i = sz/2-1; i>=0; i--)
        {
            Heapify(i) ;
        }
        return ;
    }

    void DeleteMax()
    {
        if (sz == 0)
        {
            throw out_of_range("Delete on empty heap.");
        }
        swap(0, sz-1) ;
        sz--;
        Heapify(0);
        return ;
    }

    void HeapSort(int k) // Sort k largest elemennts
    {
        int init = sz;
        while(init-sz<k)
        {
            DeleteMax() ;
        }
        sz = init;
        return ;
    }

    int kLargest( int k )
    {
        if (k>sz)
        {
            return -1;
        }
        BuildHeap() ;
        HeapSort(k) ;
        return T[sz-k] ;
    }
    
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        MaxHeap heap(nums) ;
        return heap.kLargest(k) ;
    }
};


60300