排序算法学习之路——堆排序

Z时代
2024-01-10
分类：综合

和其他排序算法一样，在这里我们先看一下堆排序的定义

堆排序（Heapsort）：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

从上面的定义的最后一句话中我们同样可以得出两个概念——大顶堆、小顶堆。

所谓大顶堆就是子节点的键值或索引总是小于它的父节点。通过大顶堆得出的序列是递增的。

所谓小顶堆就是子节点的键值或索引总是大于它的父节点。通过小顶堆得出的序列是递减的。

其实大顶堆和小顶堆的构造原理是相同的。在文章中我们只介绍其中的一种，我们就拿大顶堆为例来介绍。

下面我们来看一下堆排序的思想。

利用小顶堆堆顶记录的是最大关键字这一特性，使得每次从无序中选择最大记录变得简单。其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2...n- 1]<=R[n]; 3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。操作过程如下： 1)初始化堆：将R[1..n]构造为堆； 2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

下面我们看一个大顶堆的示例

我们看，这就是一个大顶堆。其实就是一个二叉树的表示形式，只是相对于普通的二叉树来说，这种类型的二叉树的每一个非叶子节点都大于其子节点。

下面我们通过一个图例，看一下是如何构造一个大顶堆的。

初始序列：10 6 8 7 3 30

初始二叉树：

从第一个非叶子节点开始调整

调整前

调整后

然后依次向前调整

前

后

前

后

由于节点 30 和 10互换以后，很可能导致最后一个子二叉树不满足大顶堆的性质。因此需要向下调整将其转换成大顶堆。

很幸运，在这个例子中 10---8 满足大顶堆的性质。

如果将8换成11 那还得再对其进行调整

上面就是真个大顶堆的构造过程。

构造好大顶堆以后，我们可以看到，顶部节点是整个二叉树中值最大的节点，因此我们将顶部节点和最后一个叶子节点互换。

然后我们可以将最后一个叶子节点从序列中删除掉（这里只是逻辑上的删除，并不做物理上的删除。意思就是说，在接下来的堆调整中，该节点不再参与比较和调整）。

我们看，在互换以后，该二叉树又不符合大顶堆的性质了。因此我们需要再次进行调整。

从顶部节点向下调整

此时我们看已经满足大顶堆的条件了。此时再次将顶部节点和最后一个叶子节点互换（这里需要注意：此时的最后一个叶子节点已经不是30，而是3。因为我们已经将30在逻辑上删除了）

互换完成以后

然后再次按照上述步骤依次进行调整和互换直到整个序列逻辑上全被删除为止。

整个排序过程就完成了。

下面我们通过PHP代码来实现大顶堆排序。


/**
 * 交换函数
 */
functionswap(&$arr,$a,$b){
$t = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $t;
}
/**
 * 调整一个节点和其左右子节点满足大顶堆的性质
 */
functionMakeHeapChild(&$arr,$pos,$end){
$p = false;
if($pos*2+1 <= $end){
//左右子节点相比较，找出最大节点
if($arr[$pos*2-1]>=$arr[$pos*2]){
$p = $pos*2;
        }else{
$p = $pos*2+1;
        }
    }elseif($pos*2<=$end){
$p = $pos*2;
    }
if(!$p) return$p;
//比较当前节点和其最大的子节点
if($arr[$pos-1]<=$arr[$p-1]){
        swap($arr,$pos-1,$p-1);
return$p;
    }
returnfalse;
}
functionHeapSort(&$arr){
$start = floor(count($arr)/2); //找到最后一个非叶子节点
$end = count($arr);
/*
     * 构造大顶堆
     */
while($start>0){
$p = $start;
while($p){
$p = MakeHeapChild($arr,$p,$end);
        }
$start-- ;
    }
//构造大顶堆结束
/*
     * 交换顶部节点和最后一个叶子节点 依次调整大顶堆
     */
while($end>1){
        swap($arr,0,$end-1);
$end--;
$p = 1;
while($p){
$p = MakeHeapChild($arr,$p,$end);
        }
    }
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
HeapSort($arr);
print_r($arr);

其实构造小顶堆的步骤和代码和上面的步骤大同小异。在上面代码的基础上我们修改MakeHeapChild函数就可以将大顶堆改成小顶堆，那升序排序就可以变成降序排序。


functionMakeHeapChild(&$arr,$pos,$end){
$p = false;
if($pos*2+1 <= $end){
//左右子节点相比较，找出最大节点
if($arr[$pos*2-1] < $arr[$pos*2]){   //修改一  将 >= 改成 <
$p = $pos*2;
        }else{
$p = $pos*2+1;
        }
    }elseif($pos*2<=$end){
$p = $pos*2;
    }
if(!$p) return$p;
//比较当前节点和其最大的子节点
if($arr[$pos-1] > $arr[$p-1]){      //修改二  将 <= 改成  >
        swap($arr,$pos-1,$p-1);
return$p;
    }
returnfalse;
}