class Solution {
    //用堆排序实现，删除前k-1个元素皆可以得到第k大的元素
    // 要求O(n),但是O(nlogn)可以通过
    public int findKthLargest(int[] nums, int k) {
    //     int n = nums.length;
    //     buildMaxHeap(nums);
    //     for (int i = n - 1; i > n  - k; i--) {
    //         swap(nums,0,i);
    //         heapify(nums,i,0);
    //     }
    //    return nums[0];
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)-> b-a);
        for (int i = 0; i < nums.length; i++) {
                pq.offer(nums[i]);
        }
        for (int i = 0; i < k - 1; i++) {
            pq.poll();
        } 
        
        int val = pq.poll();
        return val;
    }
    // public void buildMaxHeap(int[] arr) {
    //     int n = arr.length;
    //     for (int i = n / 2 - 1; i >= 0; i--) {
    //         heapify(arr,n,i);
    //     }
    // }
    // public void heapify(int[] arr, int n ,int i) {
    //     int largest = i;
    //     int left = 2 * i + 1;
    //     int right = 2 *i + 2;
    //     if (left < n && arr[left] > arr[largest]) {
    //         largest = left;
    //     }
    //     if (right < n &&  arr[right] > arr[largest]) {
    //         largest = right;
    //     }
    //     if (largest != i) {
    //         swap(arr,largest,i);
    //         heapify(arr,n,largest);
    //     }
    // }
    // public void swap(int[] arr, int i ,int j) {
    //     int temp = arr[i];
    //     arr[i] = arr[j];
    //     arr[j] = temp;
    // }

}