数据结构与算法(php版)排序之堆排序

yang-pig| 阅读:488 发表时间:2018-07-25 22:59:49 算法

堆分为最大堆和最小堆,其实就是完全二叉树。最大堆要求节点的元素都要不小于其孩子,最小堆要求节点元素都不大于其左右孩子,两者对左右孩子的大小关系不做任何要求,其实很好理解。有了上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。

其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。

其基本思想为(大顶堆)

  1. 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区
  2. 堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)
  3. 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成

下图来张教材的图,是整个堆排序的过程: 整个过程的核心就是先初始化大顶堆,将最大数(堆顶)的放到堆的最后一个, 堆长度-1, 继续调整成大顶堆,直至有序序列为len(array_list)-1.

企业微信截图_15325310433170.png

堆排序前42是在42后面,排序后42在42前面,因此堆排序是不稳定的。

下面举例说明:

给定一个列表array=[16,7,3,20,17,8],对其进行堆排序。

首先根据该数组元素构建一个完全二叉树,得到

2.jpg

然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:

第一步: 初始化大顶堆(从最后一个有子节点开始往上调整最大堆)

12.jpg3.jpg4.jpg

20和16交换后导致16不满足堆的性质,因此需重新调整

5.jpg

这样就得到了初始堆。

第二步: 堆顶元素R[1]与最后一个元素R[n]交换,交换后堆长度减一

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

6.jpg

第三步: 重新调整堆。此时3位于堆顶不满堆的性质,则需调整继续调整(从顶点开始往下调整)

7.jpg8.jpg

重复上面的步骤:

1.jpg2.jpg3.jpg4.jpg5.jpg6.jpg7.jpg8.jpg

注意了,现在你应该了解堆排序的思想了,给你一串列表,你也能写出&说出堆排序的过程。

在写算法的过程中,刚开始我是很懵比。后来终于看懂了。请特别特别注意: 初始化大顶堆时 是从最后一个有子节点开始往上调整最大堆。而堆顶元素(最大数)与堆最后一个数交换后,需再次调整成大顶堆,此时是从上往下调整的。

不管是初始大顶堆的从下往上调整,还是堆顶堆尾元素交换,每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换,交换之后都可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整。我在算法中是用一个while循环来解决的

开始写算法:


<?php

/**
 * 调整成大顶堆,初始堆时,从下往上;交换堆顶与堆尾后,从上往下调整
 * @param array $array:数组引用
 * @param $start:开始节点
 * @param $end:结束节点
 */
function sift_down(array &$array, $start, $end) {


    if (false === $start < $end) {
        return;
    }
    //当列表第一个是以下标0开始,结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2;
    //若下标以1开始,左孩子则为2*i,右孩子则为2*i+1;
    $left_child = 2 * $start + 1;  //左孩子的结点下标

    $right_child = $left_child + 1;


    //当结点的右孩子存在,且大于结点的左孩子时
    if($right_child < $end && $array[$right_child] > $array[$left_child]) {
        $left_child = $right_child;
    }

    if ($left_child < $end  && $array[$left_child] > $array[$start]) {//当左右孩子的最大值大于父结点时,则交换
        $temp = $array[$left_child];
        $array[$left_child] = $array[$start];
        $array[$start] = $temp;
    }

//   sift_down($array, $left_child, $end);

}

function heap_sort(array &$array) {
    //先初始化大顶堆
     $first = count($array);//最后一个有孩子的节点(//表示取整的意思)
     //第一个结点的下标为0,很多博客&课本教材是从下标1开始,无所谓吧,你随意
    //从最后一个有孩子的节点开始往上调整

     $i = floor($first / 2) + 1;

     while ($i--) {
         sift_down($array, $i, $first);
     }


    var_dump($array);

}
$array = [16, 7, 3, 20, 17, 8];

heap_sort($array);