堆的概念

堆是一种完全二叉树(除了最后一层每个节点的子节点都是满的，最后一层的节点也是集中在左边)

虽然堆是一棵二叉树，但也由于它是一棵完全二叉树的原因，可以使用一个数组来表示堆。（层次遍历）

我们常用到的堆是最大堆和最小堆

最小堆

最小堆要求，对于任意一个父结点来说，其子结点的值都大于这个父节点。

对于这个最小堆，可以用数组表示为[1,3,30,22,10,50]

最大堆

最大堆和最小堆相反，对于任意一个父结点来说，其子结点的值都小于这个父节点。

堆的操作

插入

我们看如何构建一个最小堆：

对于[30,15,5,11,22,2]

可以看出，我们依次按数组的顺序放入二叉树的节点，一旦出现子节点比父节点的值小，交换子节点和父节点。

我们称这个操作为向上堆化，堆化后的数组为[2,11,5,30,22,15]

删除

将堆树中待删除的节点A与堆树中的最后一个节点B互换，然后调整节点B到合适的位置，最后从堆树中删除排在堆数组最后的节点A。

不过在堆这个数据结构中，我们通常只需要删除堆顶元素。

堆的应用

优先级队列

实现优先级队列的方法有很多，但是用堆来实现是最直接、最高效的。堆和优先级队列非常相似，一个堆就可以看作一个优先级队列。从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。

堆排序

堆排序实际上就是不断获取堆顶元素。

对于最大堆来说，我们知道最大堆的队首元素是整个堆最大的元素，当我们删除并得到堆顶元素时，剩下的元素会重新堆化，得到一个新的堆顶元素，这样不断删除并获取堆顶元素，最终拿到的就是一个从大到小的有序序列。

当然，用数组代表堆，我们在排序的时候可以不必删除元素，只需要将原堆顶元素移动到数组末尾，将剩下的元素重新堆化，然后重复该步骤，最后就能得到一个从小到大排序的数组。

附：代码示例

实现一个完整的最大堆并堆排序一个数组

public class MaxHeap {
    private int[] heap;
    private int size;

    // 用数组来初始化一个堆
    public MaxHeap(int[] source){
        heap = source;
        size = source.length;
        heapify();
    }

    public int get(int index){
        return heap[index];
    }

    public int size() {
        return size;
    }
    //移除一个元素，并从这个元素开始向下堆化
    public int removeAt(int index){
        int node = heap[index];
        swap(index,size-1);
        size--;
        downShift(index);
        return node;
    }

    //构建堆
    public void heapify(){
        for(int i = 0; i < size; i++){
            int position = i;
            upShift(position);
        }
    }

    //向上堆化
    public void upShift(int position){
        int parent = getParent(position);
        while (position>0 && (heap[position]>heap[parent])){
            swap(position,parent);
            position = parent;
            parent = getParent(position);
        }
    }

    //向下堆化
    public void downShift(int position){
        int children1 = position*2+1;
        int children2 = position*2+2;
        while (children1<size){
            int toSwap = children1;
            if(children2<size){
                toSwap = heap[children1]>heap[children2]?children1:children2;
            }
            if(heap[toSwap]>heap[position]){
                swap(position,toSwap);
                position = toSwap;
                children1 = position*2+1;
                children2 = position*2+2;
            }else break;
        }
    }

    public void swap(int source,int destination){
        int cache = heap[source];
        heap[source] = heap[destination];
        heap[destination] = cache;
    }

    /**
     * 计算父节点下标
     */
    private int getParent(int child) {
        return (child + 1) / 2 - 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0;i<size;i++){
            sb.append(heap[i]);
            if(i!=size-1) sb.append(",");
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(new int[]{30,15,5,11,22,2});
        System.out.println(heap);
        while (heap.size()!=0){
            //堆排序得到一个序列
            int head = heap.removeAt(0);
            System.out.println(head);
        }
        //操作完后数组里元素的是从小到大排序的
        System.out.println(Arrays.toString(heap.heap));
    }
}

运行结果：

[30,22,5,11,15,2]
30
22
15
11
5
2
[2, 5, 11, 15, 22, 30]

堆排序算法Java实现

实际的堆排序中，我们肯定不用写这么长一段代码，专门把排序的逻辑提取出来就行了：

把数组看成一个最大堆（无序部分）和一个有序部分，每次将无序部分堆化一次（第一次构建堆的堆化是最耗时的，后面的堆化只需要向下堆化就好），然后第一个元素就是无序部分中最大的元素，与无序部分最后一个元素进行交换，然后并入有序部分

代码参考堆排序算法思路以及Java实现_long_lance的博客-CSDN博客，但是这里面的代码有错误，我进行了修改。

public class HeapSorting {
    public static void main(String[] args) {
        int[] a=new int[]{9,8,1,5,6,10,2};
        Sort(a);
        for(int i:a){
            System.out.println(i);
        }
    }

    //通过递归向下堆化
    public static void MaxHeapify(int[] a,int index,int size){
        int l=2*index;
        int r=2*index+1;
        int largest=index;
        if(l<=size && a[l]>a[index]){
            largest=l;
        }
        if(r<=size && a[r]>a[largest]){
            largest=r;
        }
        if(largest!=index){
            int temp=a[largest];
            a[largest]=a[index];
            a[index]=temp;
            MaxHeapify(a,largest,size);
        }
    }

    //数组堆化，注意上面实现堆的代码中构建堆是通过向上堆化，我们可以优化成将所有非叶节点向下堆化
    public static void HeapBuild(int[] a){
        for(int i=(a.length-1)/2;i>=0;i--){
            MaxHeapify(a,i,a.length-1);
        }
    }

    public static void Sort(int[] a){
        //构建堆
        HeapBuild(a);
        for(int i=a.length-1;i>=1;i--){
            //每次将堆顶元素交换到未排序部分末尾，然后再向下堆化
            int temp=a[i];
            a[i]=a[0];
            a[0]=temp;
            MaxHeapify(a,0,i-1);
        }
    }
}