7月18日学习打卡，数据结构堆

hello大家好呀，本博客目的在于记录暑假学习打卡，后续会整理成一个专栏，主要打算在暑假学习完数据结构，因此会发一些相关的数据结构实现的博客和一些刷的题，个人学习使用，也希望大家多多支持，有不足之处也请指出。本篇只讲解OJ题，关于知识点的博客稍后发出，希望大家多多支持。

面试题17.14，最小k个数

. - 力扣（LeetCode）

思路一：构建小堆

我们知道已经学习过优先级队列PriorityQueue，并且知道它底层就是堆，并且默认是小堆存放，那么，第一种思路便很清晰了，用数据集合中前K个元素来建堆，然后获取堆中前k个元素

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        for (int i = 0; i <arr.length ; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;    
    }
}

思路二：构建大堆

可以通过构建小堆解题，那么同样也可以使用大堆，第二个思路便是自己实现比较方法构建大堆，将剩余的N-K个元素依次与堆顶元素来比较，如果小于栈顶元素则替换堆顶元素，然后将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(k<=0){
            return new int[0];
        }
        int[] ret=new int[k];
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new com());
        for (int i = 0; i <k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int j = k; j <arr.length; j++) {
            if(arr[j]<priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.offer(arr[j]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;
    }
}
class com implements Comparator<Integer>{
    @Override
    public int compare(Integer t2, Integer t1) {
        return t1-t2;
    }
}

以上就是本期博客全部内容啦，明天考完科二会会把PriorityQueue详解发出来，感谢大家支持