堆排序

Sep 12, 2011 • {"display_name"=>"pensz", "login"=>"pensz", "email"=>"email", "url"=>""}

堆排序的是经典的排序方法，而堆的存储也非常的巧妙，用n个数据只需要n个结点存储，即采用长度为n+1（+1是为了下标处理的方便）的数组即可。

下面是php的实现。

// 示例数据
$data_input = array(
    null, 34, 10, 23, 58, 20, 49, 11,
);

$data_input = array(
    null, 1, 2, 3, 4, 5, 6, 7,
);

$data_input = array(
    null, 7, 6, 6, 4, 3, 2, 1, 9, 8,
);

// 排序前
var_dump($data_input);

// 堆排序，建大顶堆用来达到从小到大排序的目的
heap_sort($data_input);

// 排序后
var_dump($data_input);

/**
 * 堆排序
 */
function heap_sort(&$heap) {
    $total = count($heap) - 1; // 需要减1，原因是最大下标为 count - 1
    $half = intval($total / 2);

    // 初始化大顶堆
    for ($i=$half; $i>0; $i--) {
        heap_adjust($heap, $i, $total);
    }
    
    // 取出堆顶，放入最后，然后不断调整保证新的结构为堆
    for ($i = $total; $i > 1; $i--) {
        $temp = $heap[1];
        $heap[1] = $heap[$i];
        $heap[$i] = $temp;
        heap_adjust($heap, 1, $i-1);
    }
}

/**
 * 调整为大顶堆
 */
function heap_adjust(&$heap, $begin, $end) {
    $top_value = $heap[$begin];
    for ($i=2*$begin; $i<=$end; $i*=2) {
        if ($i < $end && $heap[$i] < $heap[$i+1]) $i++; // 右边的结点更加大，选择右边的结点和他们的父结点比较
        if ($top_value >= $heap[$i]) break; //找到了合适的位置，即 topvalue 大于左右的孩子， 为 $i 的父结点很合适
        $heap[$begin] = $heap[$i]; $begin = $i; // 否则，父结点的值为最大值，将$beign处的值设置为$i 结点上的数值，从$i接着调整堆
    }
    $heap[$begin] = $top_value; // 最后的位置保存初始时在堆顶的数据
}