堆排序（heapsort）与比较器

堆结构：

（1）逻辑概念上：完全二叉树（满二叉树或者是从左往右依次变满的二叉树）

（2）存储表示：数组从0出发的连续一段表示一颗完全二叉树，使用size描述该树有多少结点，在i位置上的结点，其左孩子下标为（2*i+1），右孩子下标为（2*i+2），父节点为（i-1）/2.

（3）分类：

大根堆：堆顶为整个堆最大的元素，同样的每个子树也满足子树的最大值是头结点的值

小根堆：堆顶为整个堆最小的元素，同样的每个子树也满足子树的最小值是头结点的值

两个重要过程：

heapinsert：向上跟父节点比较调整的过程

 /*
    从堆底向上升的过程
    某个数在arr的index位置，通过该方法找到它应该在的大根堆的位置
    方法：依次向上找父节点，直到父节点比该数大
     */
    public static void heapinsert(int[] arr, int index){
        while(arr[index] > arr[(index - 1)/2]){//包含index在0位置的情况
            swap(arr, index, (index-1)/2);
            index = (index - 1) / 2;
        }
    }

heapify：向下跟子节点比较调整的过程

 /*
    某个数在index位置，是否能往下沉找到应该在的位置
    大根堆方法：与左右孩子的最大值交换，在依次和下面的孩子比较
     */
    public static void heapify(int[] arr, int index, int heapSize){
        int left = index * 2 + 1; //左孩子的下标
        while(left < heapSize){ //如果有孩子
            //如果有右孩子，找出左右孩子中的较大的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //将较大孩子和自己比较，取较大的
            largest = arr[index] >= arr[largest] ? index : largest;
            if(index == largest) break;//如果自己比孩子都大，则停止下沉
            swap(arr, index, largest);//否则交换，继续比较
            index = largest;
            left = index * 2 + 1;
        }
    }

堆排序（由小到大——大根堆）时复：O(N*logN)，空复：O(1)

先形成堆，再从堆顶弹出元素，从后往前放入数组。

形成堆时：

法1：从数组的前面开始，依次向堆中添加元素建堆

法2：假设所有元素已经构成了堆形的树，然后从后往前下沉，先调整好局部小堆，在调整大堆。最后一层约有N/2个节点，每个结点处理1次（看一眼）；倒数第二层约有N/4个节点，每个结点处理2次（看1眼，可能向下移动1步）....所有的相加为总的操作次数（式1）。将该式左右都乘以2（式2），将两式子错位相减，可以得到最后的时间复杂度为O(N)。

 //由小到大排序
    public static void heapSortMax(int[] arr){
        if(arr == null || arr.length < 2) return;
        int heapSize = 0;

        //让数组构成大根堆，法1：O(N*logN)
//        for(int i = 0; i < arr.length; i++){//构成一个大根堆  O(N)
//            heapinsert(arr, i); //O(logN)
//        }

        //让数组构成大根堆，法2：O(N)
        for(int i = arr.length - 1; i >= 0; i--){
            heapify(arr, i, arr.length);//这里的第三个参数是堆的大小，由于是倒序依次下沉的，所以取最大值
        }
        //大根堆堆顶元素依次弹出
        heapSize = arr.length;
        swap(arr, 0, --heapSize);//如果将先swap后heapify都写到循环中，就多执行了一次没有意义的heapify
        while (heapSize > 0 ){//O(N)
            heapify(arr, 0, heapSize);//需要 len-1 次heapify即可。O(logN)
            swap(arr, 0, --heapSize);//O(1)
        }
    }

 由大到小（小根堆），Java中系统自带的优先级队列默认是小根堆

 //小根堆
    public static void heapnsert_min(int[] arr, int index){
        while (arr[index] < arr[(index - 1) / 2]){
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify_min(int[] arr, int index, int heapSize){
        int left = index * 2 + 1;
        while (left < heapSize){
            //注意这里只能是满足条件才能取右孩子，否则如果是else取右孩子，还存在右孩子不存在的情况，就会越界
            int less = (left+1 < heapSize) && arr[left + 1] < arr[left] ? left + 1 : left;
            less = arr[less] < arr[index] ? less : index;
            if(less == index) break;
            swap(arr, less, index);
            index = less;
            left = index * 2 + 1;
        }
    }
    //从大到小排序
    public static void heapSortMin(int[] arr){
        //建小根堆
        for(int i = arr.length - 1; i >= 0; i--){
            heapify_min(arr, i, arr.length);
        }
        //从堆顶依次弹出
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0){
            heapify_min(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

例题： 

/**
 * 堆排序扩展题目
 *问题描述： 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，
 * 每个元素移动的距离都不超过k，并且k相对于数组来说比较小，
 * 请选择一个合适的排序算法针对这个数据进行排序。
 * 使用结构：优先级队列（小根堆）
 * 时复：O（N*logK）
 * @param arr
 * @param k
 */

解决：使用默认的优先级队列 PriorityQueue将前（k+1）个元素建立一个小根堆，堆顶的元素一定放在arr[0]的位置，依次在向后添加新的元素构建新的小根堆，将弹出元素放入arr[1]的位置，直到整个数组的后（k+1）个元素都在堆中，然后从小到大依次弹出放入数组中。时间复杂度为O(N*logK)

如果考虑到堆的扩容问题，是成倍扩容，即扩容logN次，每次扩容完都要将原来的元素拷贝，即单次扩容代价是O（N），所以总的操作次数是O(N*logN)，每个元素均摊的扩容代价为O[(N*logN)/N] = O(logN)

 public static void sortedArrDistanceLessK(int[] arr, int k){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        for(; index < Math.min(k, arr.length); index++){//把前（k+1）个放入小根堆
            heap.add(arr[index]);
        }
        int i = 0;
        for(; index < arr.length; index++, i++){//弹出一个，添加一个，直到添加完
            arr[i] = heap.poll();//堆顶弹出放入k范围下的第一个位置
            heap.add(arr[index]);//k范围整体后移
        }
        while (!heap.isEmpty()){//堆中剩余元素按顺序弹出
            arr[i++] = heap.poll();
        }
    }

注意：

系统给的优先级队列（堆结构）与自己手写堆的区别：系统堆结构在初始建堆时结构元素大小已经固定，当如果想改变某一个数重新调整成堆时，可能需要重新扫描所有元素，heapify和heapinsert，有很高的代价，这时就需要手写堆，直接判断该变化的数是需要heapify还是heapinsert。如果只是简单的需要添加和弹出数，可以使用系统堆，涉及到更改堆元素，需要手写

比较器：

（1）实质：重载比较运算符

（2）可以很好的应用在比较特殊的排序规则上

（3）可以很好的应用在根据特殊标准排序的结构上

实现方法：自己编写一个比较器类实现Comparator<要比较的类>接口，重新compare

！！！规则：

 在Arrays.sort()、 PriorityQueue、TreeSet中都可以传入比较器对象，按照给定的要求建立。在堆中，比较器中排在前面的数应该放在上面，这样默认的小根堆也可以改成大根堆