class Solution {

 public:

     /*

      * param k : description of k

      * param nums : description of array and index 0 ~ n-1

      * return: description of return

      */

     int kthLargestElement(int k, vector<int> nums) {

         // write your code here

         int left = , right = nums.size() - ;

         while (true) {

             int pos = partition(nums, left, right);

             if (pos == k - ) return nums[pos];

             if (pos < k - ) left = pos + ;

             if (pos > k - ) right = pos - ;

         }

     }

 private:

     int partition(vector<int>& nums, int left, int right) {

         int pivot = nums[left];

         int l = left + , r = right;

         while (l <= r) {

             if (nums[l] < pivot && nums[r] > pivot)

                 swap(nums[l++], nums[r--]);

             if (nums[l] >= pivot) l++;

             if (nums[r] <= pivot) r--;

         }

         swap(nums[left], nums[r]);

         return r;

     }

 };

 class Solution {

 public:

     /*

      * param k : description of k

      * param nums : description of array and index 0 ~ n-1

      * return: description of return

      */

     inline int left(int idx) {

         return (idx << ) + ;

     }

     inline int right(int idx) {

         return (idx << ) + ;

     }

     void max_heapify(vector<int>& nums, int idx) {

         int largest = idx;

         int l = left(idx), r = right(idx);

         if (l < heap_size && nums[l] > nums[largest])

             largest = l;

         if (r < heap_size && nums[r] > nums[largest])

             largest = r;

         if (largest != idx) {

             swap(nums[idx], nums[largest]);

             max_heapify(nums, largest);

         }

     }

     void build_max_heap(vector<int>& nums) {

         heap_size = nums.size();

         for (int i = (heap_size >> ) - ; i >= ; i--)

             max_heapify(nums, i);

     }

     int kthLargestElement(int k, vector<int> nums) {

         // write your code here

         build_max_heap(nums);

         for (int i = ; i < k; i++) {

             swap(nums[], nums[heap_size - ]);

             heap_size--;

             max_heapify(nums, );

         }

         return nums[heap_size];

     }

 private:

     int heap_size;

 };