堆排序

Scroll Down

堆排序

定义

最大堆:每个结点的值都大于或等于其左右孩子结点的值
最小堆:每个结点的值都小于或等于其左右孩子结点的值

由此可知,最大堆的堆顶是堆中最大的一个值,最小堆的堆顶是堆中最小的一个值
我们把要排序的一个序列看作一个完全二叉树的层序遍历序列
例如:

[99,5,36,7,22,17,92,12,2,19,25,28,1,46]
用广义表示法可表示为:99( 5( 7(12,2), 22(19,25) ), 36( 17(28,1), 92(46,^) ) )

a

我们根据完全二叉树的性质来进行处理:最后一个非叶节点是第 2/n 个节点

建立最小堆/最大堆

  1. 首先我们从叶子节点开始,因为叶子节点没有孩子,所以其满足最小/最大堆的特性
  2. 从第一个非叶节点(2/n)开始向前遍历,如果他的儿子比他小/更大则交换位置
/**
 *  进行堆排序
 *  minheap 为真时升序,为假时降序
 */
public static void heapSort(int[] keys,boolean minheap)     //堆排序
{
    //从叶子节点上面一层开始创建最大/最小堆
    //根节点为最大/最小值
    for(int i=keys.length/2-1;i>=0;i--)             
        sift(keys,i,keys.length-1,minheap);
    //进行堆排序
    for(int i=keys.length-1;i>0;i--)
    {
        swap(keys,0,i);             //交换keys[0]和keys[i]的值
        sift(keys,0,i-1,minheap);   //向下调整,把此堆调整为最大/最小堆
    }
}
/**
 *  交换a处和b处的值
 */
public static void swap(int[] keys,int a,int b)
{
    int temp = keys[a];
    keys[a] = keys[b];
    keys[b] = temp;
}

建立最小/最大堆时,先把叶节点的上一层向下调整,保证该节点一下都是最小/最大堆,再逐步扩展到根节点

进行堆排序时,根据最大/最小堆的性质,根节点是最大/最小的,因此我们取出根节点,然后将根节点和最后一个节点进行位置的调换,再减少end的范围,保证不会再对刚刚取出的节点进行调整,最后调用向下调整函数,重新使这个堆成为最大/最小堆,这样重复下去就能保证取出的节点按升序/降序排列

/**
 *  向下调整函数,传入一个需要向下调整的节点编号parent,孩子节点范围end,从parent开始向下调整
 *  keys 数组
 *  minheap 为真时创建最小堆,为假时创建最大堆
 *  向下调整函数基于parent的孩子都是最小/最大堆
 */
public static void sift(int[] keys,int parent,int end,boolean minheap )
{
    int child=2*parent+1;       //child是parent的左孩子
    int value=keys[parent];     //记录parent的值
    while(child<=end)           //保证child在范围内
    {
        if(child<end && (minheap?keys[child]>keys[child+1]:keys[child]<keys[child+1]))  
        //找出child中比较小的那一个
            child++;
        if(minheap?value>keys[child]:value>keys[child]) //如果父母比孩子大/小
        {
            keys[parent]=keys[child];       //将较小/大的孩子节点和父亲节点交换
            parent = child;                 //孩子和父母都进入下一层
            child = 2*parent+1;
        }
        else
            break;
    }
    keys[parent] = value;                   //将原来的parent值和最小子堆中最大/小的进行交换
}

很多人就会有一个疑问,为什么parent和child比较时,不对child节点的值做任何的更改
我们记录了第一个parent节点的值为value,我们的子树已经是最小堆
只要有一个子节点比value小,就把那个子节点赋值给父节点,此处巧妙地规避了多次的交换操作

为什么要保证向下调整的节点的孩子都是最小堆

此处举一个例子,有一个堆

36( 17(28,1), 92(46,^) )

a

此处36的子堆17和92都不是最小堆

  1. 先交换36和17
  2. 再交换36和1
  3. 但是1比17要小
  4. 此处还需进行1和17的交换,就减少了建立堆的效率,这样又要重复进行向下调整

向下调整方法的递归写法

相对于非递归方法,递归方法可能更易于理解

    /**
     * 创建最小堆的向下调整方法
     * i是向下调整的节点编号
     * array是需要排序的数组
     */
    public static void shiftdown(int i,int[] array)
    {
        //如果编号i大于(length-1)/2
        //也就是叶子,就不需要向下遍历
        if(i>((array.length-1)/2))      
            return;
        int max=0;
        if(i*2+2<=(array.length)-1&&(i*2+1)<=(array.length)-1)  //防止越界
            max = array[i*2+1]<array[i*2+2]?i*2+1:i*2+2;          //选出孩子中的最大值
        else
            max = i*2+1;
        if(array[i]>array[max])       //如果该点的值大于其左孩子的值,交换位置
            {
                int temp = array[i];
                array[i] = array[max];
                array[max] = temp;
            }
            shiftdown(max, array);    //递归向其大的那个向下调整
    }
    /**
     * 创建最小堆方法
     * array是需要排序的数组
     * 进行堆排序和上述非递归类似
     */
    public static void createHeap(int[] array) 
    {
        for (int i = ((array.length-1)/2); i >=0; i--) 
            shiftdown(i, array);
    }

堆排序

    for(int i=keys.length-1;i>0;i--)
    {
        System.out.print(keys[0]);  //此处无论是输出还是放进一个顺序表中都是有序的
        swap(keys,0,i);             //交换keys[0]和keys[i]的值
        sift(keys,0,i-1,minheap);   //向下调整,把此堆调整为最大/最小堆
    }
  1. 拿走堆顶的值,其为最大/最小值
  2. 把堆顶和堆末交换位置
  3. 重新进行向下调整,调整范围防止重新调整到刚刚被交换的节点
  4. 回到一,重复执行,直到执行到数组的长度次为止,此时堆也为空