堆排序：原理解析及Java实现

在排序算法中，堆排序的出现频率相当高，相比其他排序算法如快排，他可能依赖一丢丢的数据结构基础，接下来我们详细地解释堆排的原理。

---

什么是堆？

堆其实是一种特殊的完全二叉树，在笔者之前的文章中，曾经讲解过二叉查找树，但是对于完全二叉树和满二叉树却一笔带过了，出来混总是要还的，接下来我们先把堆的概念普及一下。

完全二叉树的概念，就是自上而下，自左而右，依次的将每一个节点，垒满整棵树，这种树，称之为完全二叉树。当完全二叉树的每一个节点大于等于或者小于等于自己的左右子树时，称该完全二叉树为堆，当堆的顶端是最大的值时，称之为大顶堆，当堆的最顶端为最小值时，称之为小顶端。

我们来看看大顶堆和小顶堆的样子：

大顶堆和小顶堆

堆排序的实现逻辑

堆排序虽然引入了堆的概念，但是没有去开销额外的内存去构建一个二叉树，他只是实现了一个“逻辑堆”。

什么是逻辑堆呢？由于完全二叉树是依次垒满的二叉树，所以我们可以将垒好的二叉树从上至下，从左至右的标上序号，如此一来，很容易得出序号为i的节点，其左右子树分别为2*i+1，2*i+2。而拿大顶堆为例子，其要求便是a[i]>a[2*i+1]&&a[i]>a[2*i+2]。

好了，接下来我们看堆排序的实现步骤，首先给定一下的无序数组：

无序的数组和其“逻辑堆”

1、先构建一个大顶堆，构建一个大顶堆的步骤，需要从下至上地构建，所以我们需要从第一个非叶子节点出发：

先处理第一个非叶子节点

再处理第二个非叶子节点

调整交换节点带来的混乱

2、构建好大顶堆以后，我们再将堆顶的元素也就是最大元素放入堆的最后一个位置，从而生成了第一个有序的元素，如此再重新调整混乱的大顶堆，再依次地将调整好的大顶堆--堆顶元素放入尾部，这就有点选择排序的意思了：

将堆顶元素放在尾部

在更换堆顶元素后，进行依次堆调整

如此不停的替换，调整，最后得到有序的数组

Talk is cheap，show me the code！

堆排序的思想不是很难，关键就在于如何实现，首先有这么几个步骤：第一，构建一个大顶堆，第二，选择堆顶的元素放入数组末端，第三，调整大顶堆。

第二步是十分简单的，关键就在第三步，怎么调整大顶堆呢？出现混乱后的大顶堆，只有堆顶的元素是乱序的，此时我们需要将堆顶的元素，放到到合适的位置，这样称为一次调整。

在左右子树都是大顶堆的情况下，将左右子树更大的一个元素和堆顶元素做比较，如果比堆顶元素更大，做一个替换，再调整变动的那颗子树，这样依次就完成了一次调整。但是此调整有一个条件，也就是要求左右子树都是正常的大顶堆，所以在第一步构建大顶堆时，需要至下而上的调整，好了，逻辑已经说完，接下来上代码吧，代码中有完整注释：

public class DuiPai {
    public static void main(String[] args) {
        int a[] = {9,8,7,6,5,43,1};
        //构建大顶堆
        for(int i = a.length/2 - 1; i >= 0;i -- )
        {
            adjustDui(a,i,a.length);
        }

        //将大顶堆的顶部元素和最后的元素交换后，最后重构大顶堆
        for(int i = a.length-1;i >0;i--)
        {
            swap(a,0,i);
            adjustDui(a,0,i);
        }
        System.out.println(Arrays.toString(a));
    }



    //该方法的意义是将堆顶的左右子树中最大的值，放入堆顶
    public static void adjustDui(int a[],int start,int end)
    {

        //首先将堆顶的节点放入temp
        int temp = a[start];
        for(int i = start*2+1 ;i < end;i = i*2+1)//从左子树开始一直找到堆底
        {
            if(i+1 < end && a[i] < a[i+1] ){
                i++;
            }
            if(a[i] > temp)//此两步选出左右子树中较大的一位，然后，替换掉自己的父亲，并获取替换的位置，在下一次循环中调整变换的节点
            {
                a[start] = a[i];
                start = i;
            }
            else{
                break;
            }
        }
        a[start] = temp;
    }


    //交换数组的两个index
    public static void swap(int a[],int i,int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

文末了，觉得有帮助可以关注笔者哦！之后会推出更多文章