PS:本篇主要针对平常的算法题中，需要用到堆的时候，应该如何使用。

另外，给自己提个醒，堆是一种数据结构，只需要堆中某个节点的值总是不大于或不小于其父节点的值即可。

而堆排序则不同，在使用堆排序的过程中，比如将某个无序数组进行从低到高的排序，那么使用的是大顶堆（堆顶元素最大），然后堆顶元素和数组最后元素交换，然后将交换后的堆顶元素排除在外，进行一次堆的调整。调整到最后，堆中满足堆的性质，但是仍然无序的元素越来越少，排好序的元素则越来越多。

同时注意，如果是在多个数据中，找到K个最值，则是利用堆来维护这些最值，如找前K个最大，则使用的是最小堆，堆顶元素最小（对于堆来讲），而对于整个给定的数据来看，又是比较大的。只有你比这个堆中的最小还大，你才能入围到堆中。

一、PriorityQueue实现堆。

优先队列实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。

1.使用匿名类

最小堆（堆顶为最小元素）升序排列

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            } 
        });

最大堆（大顶堆）

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            } 
        });

优先队列的默认容量是11，因此要找前K个最值时，可以写成

PriorityQueue<Integer> heap =
                new PriorityQueue<>(k, new Comparator<Integer>() {}）;

当然也可以用默认的，然后慢慢添加元素。

2.使用Lambda表达式

以最大堆为例，就只有一行。

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)->o2-o1);

二、手撕堆

这里要强调，这里简单的实现堆的基本功能（主要是调整），要实现堆这个数据结构，则还需要进行其他方法的补充。
这个一个从小到大的排序,和排序篇记录的堆排序稍微不同，也就是边界的写法不同，for和while的区别。

public class HeapSort {

    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素,，真正的排序部分在这里
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整，j位置上的元素不再参与堆的调整
        }
    }


    //调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上，此时只有堆顶元素不符合要求）
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    //交换元素
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

三、补充-匿名内部类的分析

对于匿名内部类实现堆的写法，其具体含义如下。

有一个类实现了Comparator接口，并重写了该接口的compare方法，由于匿名内部类只是用一次，因此可以不用设计出具体的名字，毕竟还是要用一次，为了要用这个类的对象，这里可能是多态？调用的是该匿名类实现的接口的名字，以及需要传入重写的方法。

因为内部类本身是对类的功能的拓展，因此可以理解为这样的匿名内部类让上述的优先队列有了新的性质或功能，以大顶堆的写法为例，这样优先队列就可以按照元素的高低而形成堆。

补充多线程的匿名内部类的写法，有助于理解上面的匿名内部类。
下列5种写法的博客来源
方式1是最普通的继承Thread类的写法。
方式3是最普通的实现Runnable接口的写法
方式4是方式3的简化版，也和上述使用匿名内部类实现的的写法最为相似。（方法1和3是老实人写法）

public static void main(String[] args) {

        // 方式一:使用匿名内部类创建线程的子类对象
        Thread thread = new Thread() {        
            @Override
            public void run() {
                System.out.println("我的线程执行了1");
            }
        };
        thread.start();



        // 方式二:使用匿名内部类创建线程的子类匿名对象
        new Thread() {            
            @Override
            public void run() {
                System.out.println("我的线程执行了2");
            }
        }.start();



        // 方式三:使用匿名内部类的方式,创建线程执行目标类对象
        // 创建线程执行目标类对象
        Runnable runnable = new Runnable() {            
            @Override
            public void run() {
                System.out.println("我的线程执行了3");
            }
        };
        // 通过目标创建线程对象
        Thread thread2 = new Thread(runnable);
        // 开启线程
        thread2.start();



        // 方式四:使用匿名内部类的方式,创建线程执行目标类匿名对象
        // 创建线程执行目标类对象
        // 通过目标创建线程对象
        Thread thread3 = new Thread(new Runnable() {            
            @Override
            public void run() {
                System.out.println("我的线程执行了4");
            }
        });
        // 开启线程
        thread3.start();



        // 方式五:使用匿名内部类的方式,创建线程执行目标类匿名对象,并且创建的是线程的匿名对象
        // 创建线程执行目标类对象
        // 通过目标创建线程对象
        new Thread(new Runnable() {

            @Override
            public void run() {
                System.out.println("我的线程执行了5");
            }
        }).start();
    }

那么必然要补充Lambda表达式的写法
对于方式5的写法，可改写成

new Thread( () -> System.out.println("我的线程执行了6") ).start();

这里看到的一个排序的重定义