PHP算法系列教程(三)-堆排序

介紹

要介紹堆排序我們就要先了解什么是堆.

什么是堆

堆（二叉堆）可以視為一棵完全的二叉樹，完全二叉樹的一個(gè)性質(zhì)是除了最底層之外，每一層都是滿的，這使得堆可以利用數(shù)組來(lái)表示
完全二叉樹有一下幾個(gè)特點(diǎn)

1. parent(i) = floor(i/2)，i 的父節(jié)點(diǎn)下標(biāo)
2. left(i) = 2i，i 的左子節(jié)點(diǎn)下標(biāo)
3. right(i) = 2i + 1，i 的右子節(jié)點(diǎn)下標(biāo)

二叉堆一般分為兩種：最大堆和最小堆,這也是我們堆排序要使用的堆.
最大堆：

1. 最大堆中的最大元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）
2. 堆中每個(gè)父節(jié)點(diǎn)的元素值都大于等于其孩子結(jié)點(diǎn)（如果存在）

最小堆反之.

堆排序原理

堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束.
基本操作如下:

1. 最大堆調(diào)整: 將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
2. 最大堆構(gòu)造: 將堆所有數(shù)據(jù)重新排序，使其成為最大堆
3. 堆排序: 移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

代碼示例

Talk is cheap, show you my code!

/**
 * 堆排序
 * 取出最大數(shù)
 * @param $arr
 * @return mixed
 */
function heapSort($arr)
{
    buildHeap($arr);
    $length = count($arr);
    while ($length > 1) { // 長(zhǎng)度大于一才需要排序
        swap($arr, $length - 1, 0); // 將堆頂放到數(shù)組尾部(完成一次排序(取出一個(gè)最大數(shù)))
        $length --;
        adjustHeap($arr, $length, 0);
    }
    return $arr;
}

/**
 * 創(chuàng)建一個(gè)大頂堆
 * @param $arr
 */
function buildHeap(&$arr)
{
    $node = floor(count($arr) / 2) - 1 ; // 取得最后非葉子節(jié)點(diǎn)(數(shù)組0為開始故減1)
    for ($i = $node; $i >= 0; $i--) {
        adjustHeap($arr, count($arr), $i);
    }
}

/**
 * 調(diào)整堆
 * @param $arr
 * @param $length
 * @param $node
 */
function  adjustHeap(&$arr, $length, $node)
{
    list($lchild, $rchild) = getChildNode($node);
    $max = $node; // 將改節(jié)點(diǎn)設(shè)為節(jié)點(diǎn)子樹最大節(jié)點(diǎn)
    while ($lchild < $length || $rchild < $length) { // 左右子節(jié)點(diǎn)是否存在
        if ($lchild < $length && $arr[$lchild] > $arr[$max]) { // 左節(jié)點(diǎn)大于父節(jié)點(diǎn)
            $max = $lchild;
        }
        if ($rchild < $length && $arr[$rchild] > $arr[$max]) { // 右節(jié)點(diǎn)大于父節(jié)點(diǎn)
            $max = $rchild;
        }
        if ($max != $node) { // 父節(jié)點(diǎn)是否是最大節(jié)點(diǎn)
            swap($arr, $max, $node); // 若不是交換最大節(jié)點(diǎn)和父節(jié)點(diǎn)
            $node = $max; // 當(dāng)前節(jié)點(diǎn)被最大節(jié)點(diǎn)替換,查出最大節(jié)點(diǎn)兩個(gè)子節(jié)點(diǎn)
            list($lchild, $rchild) = getChildNode($node);
        } else {
            break;
        }

    }
}


function swap(&$arr, $a, $b)
{
    list($arr[$a], $arr[$b]) = [$arr[$b], $arr[$a]];
}

/**
 * 獲取左右子節(jié)點(diǎn)
 * @param $node
 * @return array
 */
function getChildNode($node)
{
    return [$node * 2 + 1, $node * 2 + 2];
}

$arr = [21, 212, 32, 43, 12, 2, 8, 10, 3];

var_dump(heapSort($arr))

結(jié)論

堆排序時(shí)間復(fù)雜度為O(nlgn), 空間復(fù)雜度只用到數(shù)組O(1);