数据结构：堆
原理：堆的结构是完全二叉树，分为最大堆（父节点大于字节点）和最小堆（父节点小于字节点）.通常可以用来计算前k个最大和最小的元素
构建最大堆：
外循环：先找到最后两个元素的父节点，父节点与子节点比较，最大值与父节点交换，然后在找到父节点的父节点循环比较，循环到第一个节点。
内循环：与父节点交换值的节点作为父节点，与子节点做比较，最大的值作为父节点。交换的子节点在作为父节点进行比较，循环到最后一个节点
php代码:
public function maxHeap($arr){
$start = intval(count($arr)/2)-1;
//外层循环，从最后两个节点的父节点开始向前
for($i=$start;$i>=0;$i--){
$this->_maxHeap($arr,$i,count($arr)-1);//var_dump($arr);
}
return $arr;
}
public function _maxHeap(&$arr,$start,$end){
//内层循环，每交换一次，交换后的子节点作为父节点向后循环调整比较
$left = ($start*2)+1;
$right = $left+1;
$max = $start;
if($start < $end){
if(!isset($arr[$left]) || $left > $end) return ;
if(!isset($arr[$right]) || $right > $end){
$max = $arr[$left] > $arr[$start] ?$left:$start;
}else{
if($arr[$left] > $arr[$right]){
$max = $arr[$left] > $arr[$start] ?$left:$start;
}else{
$max = $arr[$right] > $arr[$start]?$right:$start;
}
}
}
//交换了值，则以max为父节点的堆结构被破坏，需要再次比较得出最大值
if($max != $start){
$this->swap($arr,$max,$start);
$this->_maxHeap($arr,$max,$end);
}
}
//交换值
public function swap(&$arr,$a,$b){
$c = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $c;
}
//堆排序
public function heapSort($arr){
//先构建最大堆
$arr = $this->maxHeap($arr);
$end = count($arr)-1;
$start = 0;
while($end > $start){
//堆顶元素和最后一个元素交换
$this->swap($arr,$start,$end);
//因为交换了值，堆结构破坏，从堆顶开始修复调整,因为最后一个元素是最大值不需要动，所以长度减1
$end--;
$this->_maxHeap($arr,$start,$end);
}
return $arr;
}
//向堆中添加元素(在堆结构已经构建好的情况下)
public function addHeap($arr,$num){
array_push($arr,$num);
$end = count($arr)-1;
//向上比较，大于父节点则交换，反之则结束循环
while($end > 0){
$start = intval(($end-1)/2);
if($arr[$start] < $arr[$end]){
$this->swap($arr,$start,$end);
$end = $start;
}else{
$end = 0;
}
}
return $arr;
}
//弹出堆顶元素
public function popNum($arr){
//向交换堆顶元素和最后一个元素
$this->swap($arr,0,count($arr)-1);
//弹出最后一个元素
$num = array_pop($arr);
//从第一个元素开始构建堆
$this->_maxHeap($arr,0,count($arr)-1);
return $num;
}
