前言

堆的数据结构我们在这里不详述,堆排序总的来说一共就两步,即建立一个队使用的方式的HeapInsert和当堆顶离开时,如何维护这个堆,Heapify.
对于heap最基础的也是十分重要的一点就是父与子的关系,如下图

图片.png
如图我们可以知道
父亲的下标=(子下标-1)/2
左孩子的下标=2父亲的下标+1
右孩子的下标=2父亲的下标+2
根据上面的三个关系,我们就可以分别完成heapInsert和Heapify的方法
heapInsert的含义

for(int i=0;i<arr.length;i++)
{
heapInsert(arr,i);//以i为起点,开始向回比较,每次比较的都是(index-1)/2的关系
}

然后我们来看一下HeapInsert的方法,十分的简单

//参数,就是将arr[]传入
public static void heapInsert(int[] arr,int index)
{
     while(arr[index]>arr[(index-1)/2])
     {
             swap(arr,index,(index-1)/2);
             index=(index-1)/2;
     }
}

然后用for循环遍历它,让数组的每一个arr[]元素,都依次的向上"爬"
这个就是HeapInsert的方法

heapify

heapify的意思上当头结点发生了变化,导致当前的结构不在是堆的结构,对此进行调整,我们画一个图,来分析一下需要的参数

图片.png

public static void heapSorted(int[] arr)
    {
        if(arr==null&&arr.length==0)
        {
            return ;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }
        //这个时候我们就形成了大根堆
        int size=arr.length;
        swap(arr,0,--size);
        while(size!=0)
        {
            heapify(arr,size, 0);
            swap(arr,0,--size);
        }
    }

所以我们的核心函数就变成了上述的样子,每一次都是头和尾进行交换,同时我们要注意边界,size和循环退出的条件.
接下来就是最重要的逻辑了,怎么样实现heapify

//index表示堆顶
    public static void heapify(int[] arr,int size,int index)
    {
        int left=index*2+1;
        while(left<size)//循环条件
        {
            //这是我们看一看有没有右孩子
            //left+1=right
            //为什么是小于size而不是小于等于size
            int largest=left+1<size&&arr[left+1]>arr[left]?left+1:left;
            largest=arr[largest]>arr[index]?largest:index;
            //通过上面的两个步骤我们就可以得到了index,index的左孩子,index的右孩子,其中最大的那个
            if(largest==index)//如果最大的是index,说明交换之后还是满足堆结构的,跳出循环
            {
                break;
            }
            swap(arr,index,largest);
            index=largest;
            left=index*2+1;
        }
    }

由此我们可以进行分析以下,

• 每次比较的对象就是在index,index的左孩子,index的右孩子中产生一个最大的(我们以大顶堆为例).
• 当比较完之后,就会产生两种情况,第一种情况index就是最大的直接break
• 否则就交换,把较大的那个换到上面去
• 然后继续向下走
• 我们还需要了解到其中的循环条件为什么是left<size
  size指向的位置就是第一个不是堆结构的位置,而且堆中不存在右子树,所以 在后面我们需要left+1<size进行这个比较,这个是十分重要的

小结

int size=arr.length
swap(arr,0,--size)
while(size!=0)
{
     heapify(arr,0,size);//注意到其中的参数,index和size
     swap(arr,0,--size)
}