堆排序和Top-K问题
- 1. 堆排序
- 2. Top-K问题
1. 堆排序
堆排序是利用堆的性质进行排序的
- 如果需要升序，则建立大根堆
- 如果需要降序，则建立小根堆
下面以降序为例：
如果需要得到降序的结果，需要建立一个小根堆，将堆顶元素与最后一个元素交换（即将最大值放在数组最后），然后对新的堆顶元素进行向下调整；再将堆顶元素与倒数第二个元素交换（即将第二大的元素放在数组的倒数第二个位置），然后对新的堆顶元素进行向下调整；依次不断对堆进行调整
另外，如果按照这个思路，每次都会将一个“最小值”放到数组的末尾，那么去调整时，可能会将这个“最小值”调到其他位置去。因此，我们需要限制需要调整堆的范围，这时，就可以定义一个end变量记录需要调整堆的大小，也就是通过传参来限制usedSize的大小，从而限制向下调整堆的范围，每次将“最小值”放到数组末尾后，都将end–
本质上，就是将数组按照从后往前的顺序进行调整
那么问题来了，为什么进行降序时不建立大根堆？如果使用大根堆会怎样？
答： 如果建立大根堆，每次都能从栈顶拿到“最大值”，然后将其放到数组末尾，再进行调整。显然这样是无法在原数组基础上排序的，因为每次都把最大值放到了数组末尾。因此，如果建立大根堆来降序的话，必须额外去申请一块空间来存储每次拿到的“最大值”
例如：利用堆排序将数组{8,15,10,21,34,16,12}降序
代码实现：
public void headSort() {int end = usedSize-1;while(end > 0) {int tmp = elem[end];elem[end] = elem[0];elem[0]= tmp;shiftDown(0, end);end--;}}
2. Top-K问题
TOP-K问题 即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大，而K比较小
找到前K个最大的元素或者最小的元素，我们最容易想到的就是先将这些元素进行排序，但是当数据量较大时，这种方法就不可取了(可能数据都不能一下子全部加载到内存中)，这时最佳的办法就是，利用堆来解决这个问题
基本思路：
- 找前K个最大元素，建小根堆
- 找前K个最小元素，建大根堆
下面以找前K个最大元素为例，拿出数组中前K个元素建立小根堆，将数组中剩下元素依次与堆顶元素对比，若比堆顶元素大，则将堆顶元素出出去，将它加入堆中，调整为小根堆。重复上述步骤，直至数组遍历完，这时小根堆里的元素即前K大元素，而堆顶元素时第K大元素
时间复杂度分析：
- 前k个元素用向上调整建堆所用时间：Klog2K
- 将数组中剩下元素加入堆并向上调整所用时间：（N-K）log2K
- 总时间：Klog2K +（N-K）log2K = Nlog2 K
- 由于K的值往往比较小，所以Nlog2 K约等于N，因此Top-K问题的时间复杂度为O(N)
例如：找出数组{0，1，2，3，4，5}中前k个最大元素
class Solution {class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o1.compareTo(o2);}}public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (ret == null || k == 0) {return ret;}PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new IntCmp());for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}// K*logNfor (int i = k; i < arr.length; i++) {int peekVal = priorityQueue.peek();if (peekVal < arr[i]) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}// (N-K)logNfor (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;}
}
其实，优先级队列里建堆默认就是建小根堆，所以这里也可以不用写这个比较器
那么，现在自己来试一下找到前K小的元素吧！！！
OJ链接：面试题 17.14. 最小K个数
代码如下：
class Solution {class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}}public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (ret == null || k == 0) {return ret;}PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new IntCmp());for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}// K*logNfor (int i = k; i < arr.length; i++) {int peekVal = priorityQueue.peek();if (peekVal > arr[i]) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}// (N-K)logNfor (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;}
}
找到前K小的元素需要建立大根堆，这时就需要手动地去写一个比较器了