leetcode 215 堆排序

1??普通库函数排序：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

2??堆排序：

时间复杂度 O(nlogk)，空间复杂度 O(k)

三种函数poll,peek,element,add

共同点：

• 都是返回队列中的首个元素

不同点：

• poll：将首个元素从队列中弹出，如果队列是空的，就返回null
• peek：查看首个元素，不会移除首个元素，如果队列是空的就返回null
• element：查看首个元素，不会移除首个元素，如果队列是空的就抛出异常NoSuchElementException
• add：添加新元素在堆内
• size：表示求堆的大小

1. 首先先整理一下本题的思路，要求的是数组中第K个最大元素，也就是说要求排序之后的倒数第K个；
2. 再考虑应该是用大顶堆还是小顶堆呢？只有使用小顶堆才能每次都poll（更新）出去不是候选的数值，也就是每次都poll出去最小的第K+1个，来始终保持堆顶的元素是K个最大的元素中最小的一个；
3. 注意大顶堆和小顶堆两者的建立，之前我的博文中有提到：

Java 使用 PriorityQueue<>((x, y) -> (y - x)) 可方便实现大顶堆。

Java 使用 PriorityQueue<>() 可方便实现小顶堆。

　　　　实际上小顶堆内部默认的完整格式是：PriorityQueue<>((x, y) -> (x - y))，尤其注意全部参数的设置都是括号里面的写法；

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q=new PriorityQueue<>();
        for(int n:nums){
            q.add(n);
            if(q.size()>k){
                q.poll();
            }
        }
        return q.peek();
    }      
}

leetcode 215 堆排序

原文：https://www.cnblogs.com/sjh-dora/p/12898701.html