浅浅理解一下堆

一、堆的定义及本质

堆在Java中是以优先级队列来表现的（PrityQueue），不传入外部比较器则以小堆来实现（取出最小值）

前提：优先级队列中的元素具备比较能力（1.元素类型本身是可以比较的 2.通过构造方法传入一个外部比较器）

堆的作用：常用来在频繁变动的数据集中找出最值

堆的本质：逻辑上是完全二叉树，本质上是数组

堆的定义：

堆总是满足下列性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2、堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，有两个直接后继。

对于一个结点 2index+1 是他的左节点 2index+2是右节点 （index-1）/ 2 可以求得父节点

二、堆的核心操作

1、向下调整

当我们从堆顶取走一个最值时，这时堆的结构已经发生变化，我们往往用堆的最后一个结点来代替堆的根，但此时有可能这个值已经不满足堆的定义，我们需要对其进行向下调整，此时只有堆根部不满足堆的定义

我们此时对根部进行调整

我们首先想到在根的左右结点中找到最小的值来判断是否大于根，如果根已经是最小值，则满足堆的定义，不需要进行交换，否则根与最小值进行交换

 //对堆的根部进行向下调整
    //结束调整的条件？  已经满足堆的结构，无需调整    当前结点已经是叶子结点，下边没有节点，无需调整
    public void justDown(int arr[],int size,int index){
        int left=2*index+1;//判断左子树是否存在，如果没有左子树，必没有右子树（完全二叉树性质）
        while (left<size){
            int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找出左右子树中的最小值
            int largest=arr[index]<=arr[min]?index:min;//在根和最小值中再找出最小值
            if (largest==index) break;//如果根就是最小值 堆结构已满足 退出循环
            swap(arr,index,min);  //不满足交换根和最小值，根等于最小值进行下一次调整
            index=min;
            left=index*2+1;
        }
    }

    private void swap(int[] arr, int index, int min) {
        int temp=arr[index];
        arr[index]=arr[min];
        arr[min]=temp;
    }

2、堆的创建

在我们已经掌握向下调整的情况下，如何将一个完全二叉树调整为堆呢？

我们可以对每个结点进行向下调整，使每个结点都满足堆的定义

但我们知道向下调整的结束条件是当前结点已经满足堆的结构或者当前结点是叶子结点，因此我们没有必要对叶子结点进行调整，而在完全二叉树中我们很容易找到最后一个结点（size-1）是最后一个结点的下标 而他的父节点是（size-1-1）/ 2 那么自他的父节点之后就全是叶子节点

public void creatHeap(int[] arr,int size){
        for (int i=(size-2)/2;i>=0;i--){
            justDown(arr,size,i);
        }
    }

为什么从上到下不行？因为我们向下调整是由要求的，必须左右子树已经是一个堆结构了 如果不理解可以画图。。

在经历一次向下调整时我们发现最小的1永远没有走到顶部的机会，为什么呢，因为我们没有满足向下调整的定义。没有找到真正最小的那个数调整到堆顶

3、向上调整

在我们创建完成一个堆的时候，往往需要往堆里边添加新的元素，由于我们从数组【0，size）是已经创建好的堆结构，在我们新添加一个元素时，往往需要向上调整

public void justUp(int[] arr,int index){
        int parent=(index-1)/2;//父节点下标
        while (arr[index]>arr[parent]){//当子节点大于父节点时我们需要向上调整
            swap(arr,index,parent);
            index=parent;//新的Index是他的父节点
            parent=(index-1)/2;//新的parent结点
        }
    }

三、堆的比较器传入及堆中简单函数的实现

假设当前有一个person类，里边的属性有姓名和年龄，此时person是默认不支持比较的

 public class person{
        String name;
        int age;
    }

在不修改person类的情况下我们如何实现比较年龄呢？

答案是采用外部比较器

static class PersonComparator implements Comparator<Person>{

        @Override
        public int compare(Person o1, Person o2) {
            return o1.age-o2.age;
        }
    }

 static class PersonComparator implements Comparator<Person>{

        @Override
        public int compare(Person o1, Person o2) {
            return o1.age-o2.age;
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Person> pq=new PriorityQueue(new PersonComparator());
        pq.add(new Person("小明",11));
        pq.add(new Person("小红花",9));
        pq.add(new Person("小刚",21));
        while (!pq.isEmpty()){
            System.out.println(pq.poll().toString());
        }

    }

堆的简单函数全实现：

public class MyPriorityQueue{
    long arr[];
    int size;
    public MyPriorityQueue(){//由于我们的元素类型是long类型没有采用泛型，所以不涉及传入比较器
        arr=new long[20];
        size=0;
    }

    public void add(long val){//往堆中加入一个元素
        ensureCapacity();//保证数组空间够用
        arr[size]=val;
        justUp(arr,size);//新加入的元素需要向上调整维持一个堆结构
        size++;
    }

    public long peek(){//查看堆顶部元素
        if (size<0){
            throw new RuntimeException("队列是空的");
        }
        return arr[0];
    }

    public long poll(){//弹出堆顶部的元素
        if (size<0){
            throw new RuntimeException("队列是空的");
        }
        long res=arr[0];//先记录需要返回的元素
        arr[0]=arr[size-1];//把最后一个元素调整到堆的顶部并向下调整
        arr[size-1]=0;//最后一个元素交换到堆顶，那么它就要改为默认值
        size--;
        justDown(arr,size,0);
        return res;
    }

    public int size(){
        return size;
    }

    private void justDown(long[] arr, int size, int index) {
        int left=index*2+1;
        while (left<size){//如果还有子节点（不是叶子节点）
            int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找到左右子结点中的最小值
            int largest=arr[min]<arr[index]?min:index;//找到最小的值
            if (largest==index) break;//如果index本身就是最小值说明他已经满足堆结构不需要调整
            swap(arr,min,index);//交换index和最小值
            index=min;//新的index
            left=index*2+1;//新的最小值
        }
    }

    public void check(){//检查是否满足堆结构
        if (size<0||size>arr.length){
            throw new RuntimeException("size越界");
        }
        for (int i=0;i<size;i++){
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left >= size) {
                // 说明是叶子，跳过
                continue;
            }

            // 左孩子破坏了规则
            if (arr[i] > arr[left]) {
                throw new RuntimeException(String.format("[%d] 位置的值大于其左孩子的值了", i));
            }

            // 右孩子破坏了规则
            if (right < size && arr[i] > arr[right]) {
                throw new RuntimeException(String.format("[%d] 位置的值大于其右孩子的值了", i));
            }
        }
    }

    private void justUp(long[] arr, int index) {
       while (index!=0){
           int parent=(index-1)/2;
           if (arr[parent]<=arr[index]) return;
           swap(arr,index,parent);
           index=parent;
       }
    }

    public boolean isEmpty(){
        return size==0;
    }

    private void ensureCapacity() {
        if (size<arr.length) return;
        arr= Arrays.copyOf(arr,size*2);
    }

    public void swap(long[] arr,int i,int j){
        long temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

四、堆的应用

1、用于OS调度进程

2、topk问题

topk问题其实在现实生活有很多场景，比如说淘宝的好物top10等等

假如说我们要在很多数据中找到前k个最大的数 我们有什么思路呢？

1.对所有的数据进行排序再取出前十

这种方法无疑消耗的时间成本和空间成本是是非常高的

时间复杂度达到了O（N*logN） 空间复杂度是O（N）

2.把所有的数据入堆，在取出前k个元素

第二种方法的时间复杂度相较于第一种减少了很多 大概是O（k*logN），但我们忽略了在数据非常庞大时，堆的向下调整操作往往也需要耗费大量时间，并且空间复杂度也达到了惊人的O（N）

3.我们采用建小堆，小堆的size就是k，如果当前元素比小堆中最小元素大，我们就把它加进去，到最后堆里的元素就是topk

并且空间复杂度也只有O（k）

代码如下：

public class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k==0){ //处理特殊情况，防止堆为空造成的index越界
            return new int[0];
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>(((o1, o2) -> o2-o1));
        for (int i=0;i<k;i++){ //添加k个元素进入堆
            pq.add(arr[i]);
        }
        for (int i=k;i<arr.length;i++){//维持堆中的元素是最小的k个
            if (arr[i]<pq.peek()){
                pq.poll();
                pq.add(arr[i]);
            }
        }
        int[] res=new int[k];//返回这k个元素
        int i=0;
        while (!pq.isEmpty()){
            res[i++]=pq.poll();
        }
        return res;

    }
}

3、堆排序

堆排序是一种利用堆结构找到最值然后不断取出进行排序，本质上是一种选择排序，不过由于堆找出并维持最值的时间复杂度是O（N*longN）所以他是一种高效的排序

我们把需要排序的数组看 无序加有序的形式 一旦我们找到最值元素 我们就把它交换到最后边

因此总的排序要进行arr.length-1次交换

public void swap(long[] arr,int i,int j){
        long temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public long[] heapSort(long[] nums){
        //首先我们需要建立大堆，把大的元素找出并交换到最后边
        buildHeap(nums);
        for (int i=0;i<nums.length-1;i++){
            swap(nums,0,arr.length-1-i);
            justDown(nums,arr.length-i-1,0);
        }
        return nums;
    }

    private void buildHeap(long[] nums) {
        for (int i=(nums.length-2)/2;i>=0;i--){
            justDown(nums,nums.length,i);
        }
    }