Perl算法实践---堆排序
今天我们介绍另一种排序方法--堆排序。堆排序具有空间原址性， 即任何时候， 我们只需要数个额外的元素空间来存储临时数据，就可以达到排序的结果。
堆排序使用的数据结构是二叉堆， 也可以理解成近似的完全二叉树， 在堆排序中， 我们往往使用的是最大堆， 也就是在二叉堆中， 每个结点都小于等于其父结点。
当我们将数据构造成最大堆时， 我们的数据就已经排序完成了。
在构造最大堆时， 最重要也是最核心的步骤就是维护堆， 在我们新添加一个数据进来时， 我们需要从根结点， 依次来对该数据进行比较， 如果该数据小于该结点， 则下沉继续比较，如果大于该结点， 则交换结点， 并重新维护。 通过维护堆这一过程， 来确保新的堆符合最大堆的特性。
整个堆排序过程， 其实就是逐步将数据加入堆中， 通过维护堆的过程， 来一步步的将数据插入堆中， 直至所有的数据都被存入最大堆中。
以下是具体的实现方法：
对于最大堆的数据结点下标, 为了方便， 我们这里下标统一从1开始计算， 实际应用中可以根据0开始， 但要小心处理：
当一个结点下标为i时， 他的父结点下标为 int(i/2), 他的左子结点下标为2i， 右子结点下标为2i+1。
#我们有如下数据：
my @nums = (0,44,1,2,27,5,19,4); #为了方便，我们从下标1开始计算， 因此第一位直接忽略
my $size = @nums - 1;
#首先我们实现维护堆的过程：
sub max_heapify{
my ($nums_ref, $index) = @_;
my $left = 2 * $index;
my $right = 2 * $index + 1;
my $largest;
if ($left <= $size && $nums_ref->[$left] > $nums_ref->[$index]) {
$largest = $left;
}else{
$largest = $index;
}
if ($right <= $size && $nums_ref->[$right] > $nums_ref->[$largest] ){
$largest = $right;
}
if ($largest != $index ){
($nums_ref->[$index], $nums_ref->[$largest]) = ($nums_ref->[$largest], $nums_ref->[$index]);
max_heapify($nums_ref, $largest);
}
}
#构造最大堆：
sub build_max_heap{
my $nums_ref = shift;
my $size = @$nums_ref - 1;
for my $index(reverse (1...int($size / 2) )){
max_heapify($nums_ref, $index);
}
}
build_max_heap(\@nums);
#得到最大堆后， 我们只需要从根结点逐个取得每个元素， 即可得到排序完的内容,
#需要注意的是， 每次我们取完一个结点时， 需要对最大堆来进行重新维护操作， 使剩余元素仍然满足最大堆的特性
for my $index(reverse (1...$size) ){
($nums[$index], $nums[1]) = ($nums[1], $nums[$index]);
$size--;
max_heapify(\@nums, 1);
}
print @nums;