PHP算法系列教程(三)-堆排序
介绍
要介绍堆排序我们就要先了解什么是堆.
什么是堆
堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个性质是除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示
完全二叉树有一下几个特点
- parent(i) = floor(i/2)，i 的父节点下标
- left(i) = 2i，i 的左子节点下标
- right(i) = 2i + 1，i 的右子节点下标
二叉堆一般分为两种：最大堆和最小堆,这也是我们堆排序要使用的堆.
最大堆：
- 最大堆中的最大元素值出现在根结点（堆顶）
- 堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
最小堆反之.
堆排序原理
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束.
基本操作如下:
- 最大堆调整: 将堆的末端子节点作调整，使得子节点永远小于父节点
- 最大堆构造: 将堆所有数据重新排序，使其成为最大堆
- 堆排序: 移除位在第一个数据的根节点，并做最大堆调整的递归运算
代码示例
Talk is cheap, show you my code!
/**
* 堆排序
* 取出最大数
* @param $arr
* @return mixed
*/
function heapSort($arr)
{
buildHeap($arr);
$length = count($arr);
while ($length > 1) { // 长度大于一才需要排序
swap($arr, $length - 1, 0); // 将堆顶放到数组尾部(完成一次排序(取出一个最大数))
$length --;
adjustHeap($arr, $length, 0);
}
return $arr;
}
/**
* 创建一个大顶堆
* @param $arr
*/
function buildHeap(&$arr)
{
$node = floor(count($arr) / 2) - 1 ; // 取得最后非叶子节点(数组0为开始故减1)
for ($i = $node; $i >= 0; $i--) {
adjustHeap($arr, count($arr), $i);
}
}
/**
* 调整堆
* @param $arr
* @param $length
* @param $node
*/
function adjustHeap(&$arr, $length, $node)
{
list($lchild, $rchild) = getChildNode($node);
$max = $node; // 将改节点设为节点子树最大节点
while ($lchild < $length || $rchild < $length) { // 左右子节点是否存在
if ($lchild < $length && $arr[$lchild] > $arr[$max]) { // 左节点大于父节点
$max = $lchild;
}
if ($rchild < $length && $arr[$rchild] > $arr[$max]) { // 右节点大于父节点
$max = $rchild;
}
if ($max != $node) { // 父节点是否是最大节点
swap($arr, $max, $node); // 若不是交换最大节点和父节点
$node = $max; // 当前节点被最大节点替换,查出最大节点两个子节点
list($lchild, $rchild) = getChildNode($node);
} else {
break;
}
}
}
function swap(&$arr, $a, $b)
{
list($arr[$a], $arr[$b]) = [$arr[$b], $arr[$a]];
}
/**
* 获取左右子节点
* @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))
结论
堆排序时间复杂度为O(nlgn), 空间复杂度只用到数组O(1);
