<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 {
        private:
            vector<int>heap;

        public:
            MaxHeap() {
                heap = vector<int>();
            }

            void heapifyUp() {
                int index = heap.size() - 1, parent;

                while (index > 0) {
                    parent = (index - 1) / 2;

                    if (heap[index] > heap[parent]) {
                        swap(heap[index], heap[parent]);

                        index = parent;
                    } else {
                        break;
                    }
                }
            }

            void heapifyDown() {
                int index = 0, left, right, size = heap.size(), candidate;

                while (index < size) {
                    left = 2*index + 1;
                    right = 2*index + 2;

                    if (right < size) {
                        if (heap[index] < heap[left] && heap[index] < heap[right]) {
                            if (heap[left] >= heap[right]) {
                                candidate = left;
                            } else {
                                candidate = right;
                            }
                        } else if (heap[index] < heap[left]) {
                            candidate = left;
                        } else if (heap[index] < heap[right]) {
                            candidate = right;
                        } else {
                            break;
                        }
                    } else if (left < size && heap[index] < heap[left]) {
                        candidate = left;
                    } else {
                        break;
                    }
                    
                    swap(heap[index], heap[candidate]);
                    index = candidate;
                }
            }

            void insert(int val) {
                heap.push_back(val);
                heapifyUp();
            }

            void deleteMax() {
                if (heap.size() == 0) {
                    return;
                }

                heap[0] = heap[heap.size()-1];
                heap.resize(heap.size()-1);

                heapifyDown();
            }

            int getMax() {
                if (heap.size() == 0) {
                    return 0;
                }
                
                return heap[0];
            }

            int getSize() {
                return heap.size();
            }
    };

    int findKthLargest(vector<int>& nums, int k) {
        MaxHeap heap = MaxHeap();
        int N = nums.size();

        for (int i = 0; i < N; i++) {
            heap.insert(nums[i]);
        }
        
        while (k > 1) {
            k--;
            
            heap.deleteMax();
        }

        return heap.getMax();
    }
};
63200