堆排序

1.前提知识

堆：（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

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

• 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

优先队列(priority queue)

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

a.完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树（一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。）而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）

(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。

b.小根堆和大根堆

假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。

同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为大根堆。

2.一些规律

最后一个非叶节点的位置为nums.length-1，所有拥有左右子节点的节点与子节点的位置关系为，假设子节点的编号为n，那么左子节点的编号为2n+1右节点的编号为2(n+1)

然后具体的做法为1.先建立大（小）顶堆，2.交换堆顶的位置和调整整个堆，每调整一次堆的长度就减少一，直到堆的大小为0或1结束

3.先实现大顶堆

public static void main(String[] args) {
        int[] array = new int[]{1,3,4,2,5};
        heapsort(array);

其结构就相当于

image.png

然后我们先实现大顶堆

  private static int[] heapsort(int[] array) {
        buildBigheap(array);
    }

从最后一个非叶节点的节点开始调整，一直调整到根节点，这样大顶堆就建立好了

private static void buildBigheap(int[] array) {
        for(int i=array.length/2-1;i>-1;i--){ //从最后一个非叶节点的节点开始调整，一直调整到根节点
            adjustheap(array,i,array.length);  
        }

然后是具体的调整过程：

private static void adjustheap(int[] array, int i,int end) {
        //如果没有左右子树或者左右子树现在已经是拍好序的顺序
        if(2*i+1 >=end){
            return;
        }else if(2*(i+1)>=end){
            if(array[2*i+1]>=array[i]){
                swap(array,2*i+1,i);
            }
        }else{
            //根已为最大
            if(array[i]>=array[2*i+1]&&array[i]>=array[2*(i+1)]){
                return;
                //左子树最大,交换后去排列左边
            }else if(array[2*i+1]>=array[i]&&array[2*i+1]>=array[2*(i+1)]){
                swap(array,2*i+1,i);
                adjustheap(array,2*i+1,end);
                //右子树最大，交换后去排列右边
            }else{
                swap(array,2*(i+1),i);
                adjustheap(array,2*(i+1),end);
            }
        }
    }

**具体就是先判断现在调整的位置，

A状况说明(分成两种情况：1.该节点是叶节点，2，该节点往后的子节点已经被拍好序了）
B状况说明(因为当一个节点只含有左子节点可以用的时候，那么他的右节点一定是空或者已经排好序了）
C状况说明(如果根最大什么都不用做，直接返回，如果左子节点最大，那么与根交换，并对左子节点的剩余节点进行调整，同理可得右子节点）
OK
现在做完这一步我们可以看一下数组结构

image.png
image.png
这个时候的根是最大的也就是已经实现了大顶堆

4.交换堆顶元素与最后一个元素，实现排序

其实这一过程就是交换调整，每一次交换都会使堆的需排序的大小减一，那么很容易就想到当堆大小为1时，调整完毕，所以用一个for循环for i array.length ->1

 for(int i =array.length-1;i>0;i--){
            swap(array,i,0);  //交换栈顶元素与堆的最后一个数据（每次最后一个数据都会减一）
            adjustheap(array,0,i);  //调整堆为大顶堆
        }

例如第一次交换后的数据为

image.png

然后调整完的数据为：

image.png

这样做完后所有的序都已经排好了

完整代码

public static void main(String[] args) {
        int[] array = new int[]{1,3,4,2,5};
        heapsort(array);
        for(int i=0;i<array.length;i++){
            System.out.printf(array[i]+" ");
        }
    }

    private static int[] heapsort(int[] array) {
        buildBigheap(array);
        return array;
    }

    private static void buildBigheap(int[] array) {
        for(int i=array.length/2-1;i>-1;i--){
            adjustheap(array,i,array.length);
        }

        for(int i =array.length-1;i>0;i--){
            swap(array,i,0);
            adjustheap(array,0,i);
        }
    }
    private static void adjustheap(int[] array, int i,int end) {
        //如果没有左右子树或者左右子树现在已经是拍好序的顺序
        if(2*i+1 >=end){
            return;
        }else if(2*(i+1)>=end){
            if(array[2*i+1]>=array[i]){
                swap(array,2*i+1,i);
            }
        }else{
            //根已为最大
            if(array[i]>=array[2*i+1]&&array[i]>=array[2*(i+1)]){
                return;
                //左子树最大,交换后去排列左边
            }else if(array[2*i+1]>=array[i]&&array[2*i+1]>=array[2*(i+1)]){
                swap(array,2*i+1,i);
                adjustheap(array,2*i+1,end);
                //右子树最大，交换后去排列右边
            }else{
                swap(array,2*(i+1),i);
                adjustheap(array,2*(i+1),end);
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] =array[j];
        array[j] = temp;
    }