堆可以视为一棵完全的二叉树,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素。
数组与堆之间的关系：
二叉堆一般分为两种：最大堆和最小堆。
最大堆：堆中每个父节点的元素值都大于等于其孩子结点（如果存在）；
最小堆：堆中每个父节点的元素值都小于等于其孩子结点（如果存在）；
什么是堆排序
堆排序（假设利用最大堆）就是把堆顶的最大数取出,将剩余的堆继续调整为最大堆
堆排序算法
建堆：建堆是不断调整堆的过程，从 len/2 处开始调整，一直到第一个节点，此处 len 是堆中元素的个数。建堆的过程是线性的过程，从 len/2 到 0 处一直调用调整堆的过程，相当于 o(h1) + o(h2) …+ o(hlen/2) 其中 h 表示节点的深度，len/2 表示节点的个数，这是一个求和的过程，结果是线性的 O(n)。
调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点 left(i) , right(i)，选出三者最大(或者最小)者，如果最大（小）
值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是 logn 的操作，因
为是沿着深度方向进行调整的。
堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面 len-1 个节点继续进行堆调整的过
程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是 O(nlogn)。因为建堆的时间复杂度是 O(n)（调用一次）；调整堆的时间复杂度是 logn，调
用了 n-1 次，所以堆排序的时间复杂度是O(nlogn)。
例子：
= 0; $i --)
{
heap_adjust($arr, $i, $count);
}
// 调整堆
for($i = $count - 1; $i >= 0; $i--)
{
//将堆顶元素与最后一个元素交换
swap($arr,0,$i);
heap_adjust($arr,0,$i - 1);
}
}
/**
* 交换2个值
* @param array $arr
* @param int $a 数组下标
* @param int $b 数组下标
*/
function swap(array &$arr, $a, $b)
{
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
/**
* 交换2个值
* @param array $arr
* @param int $start 数组下标
* @param int $end 数组下标
*/
function heap_adjust(array &$arr, $start, $end)
{
$temp = $arr[$start];
//沿关键字较大的孩子节点向下筛选，这里数组开始下标识0
for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1)
{
if($j != $end && $arr[$j] < $arr[$j + 1])
{
$j ++;
}
if($temp < $arr[$j])
{
//将根节点设置为子节点的较大值
$arr[$start] = $arr[$j];
$start = $j;
}
}
$arr[$start] = $temp;
}
// 使用
$arr = array(8,4,2,9,3,7,1,6,5);
heap_sort($arr);
print_r($arr);输出：
Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 [8] => 9 )
时间复杂度分析
总体上来说，堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。
堆排序是一种不稳定排序方法(排序前后相同元素的前后顺序可能改变)。
相关推荐：
