算法进阶之路（三）:堆的数据结构、排序及应用

一、堆的数据结构

堆就是用数组实现的二叉树，主要分为两种：最大堆和最小堆。两者的差别在于节点的排序方式，在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。
需要注意的是，堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。例如：

二、堆和二叉树的区别

1.节点的顺序，在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

2.内存占用，普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。

3.平衡，二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

4.搜索，在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

三、代码实现堆

实现思路在注释中有完整说明：

/**
 * @author ljx
 * @Description: 自定义数组实现最大堆
 * @date 2021/10/21 10:41 上午
 */
public class MaxHeap {

    private int[] heap;
    private int limit;
    private int heapSize;

    public MaxHeap(int limit){
        heap = new int[limit];
        this.limit = limit;
        heapSize = 0;
    }

    // 往堆中添加元素
    public void push(int value){
        if(heapSize==limit){
            throw new IndexOutOfBoundsException("堆空间已满，无法添加");
        }
        heap[heapSize] = value;
        heapInsert(heap,heapSize++);
    }
    // 弹出元素
    public int pop(){
        // 弹出当前根节点的值
        int root = heap[0];
        // 将数组中最后一个节点放置到根节点
        swap(heap,0,--heapSize);
        // 最后一个元素移除
        heap[heapSize]=0;
        // 重新调整当前堆为最大堆
        heapify(heap,0,heapSize);
        return root;
    }

    // 向堆中插入元素，并完成最大堆的构建
    private void heapInsert(int[] arr, int index){
        // 计算出父节点的索引
        int parent = (index-1)/2;
        // 比较当前节点和父节点的大小，当前节点比父节点大时，当前节点和父节点交换位置
        // 只有两种情况下，停止循环 1.当前节点小于父节点 2.循环已经到达父节点,此时自己肯定不小于自己,因为两个条件都可以通过arr[index]<=arr[parent]来跳出循环
        while(arr[index]>arr[parent]){
            // 当前节点大于等于父节点，则和父节点交换位置
            swap(arr,index,parent);
            // 同时当前节点的索引位置调整到父节点的索引
            index = (index-1)/2;
        }
    }

    // 将一个数组调整为最大堆
    public void heapify(int[] arr,int index,int heapSize){
        // 从根节点开始，和两个子节点比较，如果子节点更大，则调换位置,直到没有子节点为止
        // 分别计算出两个子节点的索引位置
        int left = index*2+1;
        // 子节点不存在时跳出循环,只要左节点小于父节点，就一直循环
        while(left<heapSize){
            // 右边的子节点存在时，比较得出两个子节点的最大值
            int latest = left+1<heapSize&&arr[left]>arr[left+1]?left:left+1;
            // 再比较子节点和父节点的大小
            latest = arr[latest]>arr[index]?latest:index;
            // 父节点大于两个子节点时，跳出循环
            if(latest==index){
                break;
            }
            // 父节点小于子节点时，两个节点交换位置
            swap(arr,index,latest);
            // 同时index位置下沉
            index = latest;
            // 重新计算左节点的位置
            left = index*2+1;
        }

    }

    // 完成堆排序
    public void heapSort(int[] arr){
        if(arr==null||arr.length==1){
            return;
        }
        // 先将数组中的每一个元素放在最大堆中
        // 时间复杂度 O(N*logN)
        for(int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }
//        // 如果每次给的是数组中的一批数据，而不是一个个给的话，上述循环，可以优化如下,
//        for(int i=arr.length-1;i>=0;i--){
//            heapify(arr,i,arr.length);
//        }

        int heapSize = arr.length;
        // 每次把最大数，即0元素位置的数调整到数组的末尾,同时heapSize减1
        swap(arr,0,--heapSize);
        // 一直调整，直到heapSize>0
        while (heapSize>0){
            // 重新调整堆
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }

    }
    // 交换数组中两个位置的值
    private void swap(int[] arr, int son, int parent) {
        // 如果是值相同，或者是同一位置的，则无需交换
        if(arr[son]==arr[parent]||son == parent){
            return;
        }
        arr[son]=arr[son]^arr[parent];
        arr[parent]=arr[son]^arr[parent];
        arr[son]=arr[son]^arr[parent];
    }

    public int[] getHeap() {
        return heap;
    }

    public void setHeap(int[] heap) {
        this.heap = heap;
    }

    public int getLimit() {
        return limit;
    }

    public void setLimit(int limit) {
        this.limit = limit;
    }

    public int getHeapSize() {
        return heapSize;
    }

    public void setHeapSize(int heapSize) {
        this.heapSize = heapSize;
    }
}

测试代码：

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.push(1);
        maxHeap.push(9);
        maxHeap.push(6);
        maxHeap.push(3);
        maxHeap.push(7);
        maxHeap.push(8);
        System.out.println("打印堆中数据：" + Arrays.toString(maxHeap.getHeap()));
        System.out.println("打印取出的堆中最大数据：" + maxHeap.pop());
        System.out.println("打印取出堆中最大数据后，堆的数据：" + Arrays.toString(maxHeap.getHeap()));
        maxHeap.heapSort(maxHeap.getHeap());
        System.out.println("打印排序后堆的数据：" + Arrays.toString(maxHeap.getHeap()));
    }

测试结果：

分析可知，测试结果完全符合预期，代码无误。

四、总结

1.堆结构总结

2.堆排序总结

五、面试题练习

Java中也有堆的实现，java.util.PriorityQueue，默认是最小堆，不过可以通过设置内部的参数构造器comparator，来生成最大堆，下面的面试题中会带领大家使用一下此类。

解题思路及代码：

    private static void sort(int[] arr,int k){
        // 默认最小堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
        // 先往最小堆中添加k个元素
        int index = 0;
        for(;index<=Math.min(k,arr.length-1);index++){
            priorityQueue.add(arr[index]);
        }
        // 依次往数组中取出一个元素，再放置一个元素，直到数组遍历完成,则每次取出的最下值即是数组中顺序
        int i=0;
        while(index<arr.length){
            arr[i++]=priorityQueue.poll().intValue();
            priorityQueue.add(arr[index++]);
        }
        // 数组遍历完成后，i到arr.length位置的元素还保存在最小堆中，此时全部取出
        while(i<arr.length){
            arr[i++]=priorityQueue.poll().intValue();
        }
    }