PHP算法系列教程(三)-堆排序
介紹
要介紹堆排序我們就要先了解什么是堆.
什么是堆
堆（二叉堆）可以視為一棵完全的二叉樹(shù)，完全二叉樹(shù)的一個(gè)性質(zhì)是除了最底層之外古胆，每一層都是滿的喊儡，這使得堆可以利用數(shù)組來(lái)表示
完全二叉樹(shù)有一下幾個(gè)特點(diǎn)
- parent(i) = floor(i/2)愚臀，i 的父節(jié)點(diǎn)下標(biāo)
- left(i) = 2i科雳，i 的左子節(jié)點(diǎn)下標(biāo)
- right(i) = 2i + 1，i 的右子節(jié)點(diǎn)下標(biāo)
二叉堆一般分為兩種：最大堆和最小堆,這也是我們堆排序要使用的堆.
最大堆：
- 最大堆中的最大元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）
- 堆中每個(gè)父節(jié)點(diǎn)的元素值都大于等于其孩子結(jié)點(diǎn)（如果存在）
最小堆反之.
堆排序原理
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出蕾域，將剩余的堆繼續(xù)調(diào)整為最大堆敦间，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束.
基本操作如下:
- 最大堆調(diào)整: 將堆的末端子節(jié)點(diǎn)作調(diào)整束铭，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
- 最大堆構(gòu)造: 將堆所有數(shù)據(jù)重新排序廓块，使其成為最大堆
- 堆排序: 移除位在第一個(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為開(kāi)始故減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)子樹(shù)最大節(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);
