这个堆并不是堆栈中那个堆，英文我们称之为Heap。堆就是完全二叉树，至于完全二叉树是什么鬼东西，有为青年可能还记得，其余青年可能忘的差不多了，然后自己默默上前面翻去。

    堆分为两类，最大堆和最小堆。最大堆就是根结点的元素最大，然后以从上到下从左往右数据递减，最小堆呢就恰恰相反。这里值得注意的是堆的两个特性：

    • 序号为x的结点，如果有左子树，那么左子树序号一定是2x；如果有右子树，那么右子树序号一定是2x+1
    • 序号为x的结点，如果有父结点则其序号为floor( x / 2 )。floor表示不大于x的最大整数

    像下面这货，就是典型的最小堆：

    12. 数据结构之最大堆和最小堆 - 图1

    最大堆自然就与最小堆相反：

    12. 数据结构之最大堆和最小堆 - 图2

    从图中可以观察到的是最大堆的任意一个结点的左右子树（只要存在）都比该结点要小，最小堆的任意一个结点的左右子树（只要存在）都比该结点要大。

    那么话说回来，“堆”这玩意到底有啥用？

    12. 数据结构之最大堆和最小堆 - 图3

    其实，最大的作用就是堆排序！堆排序是一种不稳定排序，平均时间复杂度为( nlogn )，其中logn是用于构建堆，n用于排序。这种数据结构本身在我们需要top k这种排序的时候会优势比较明显，非常屌，值得掌握。

    假如说我们有array( 50, 10, 90, 30, 70, 40, 80, 60, 20 )，然后需要将这个一维数组构建成最大堆，代码大概如下：

    1. <?php
    2. class Base{
    3.   public $fn = null;
    4.     public $size = 0;
    5.     public $element = [];
    6.     public function __construct(){
    7.         $this->element[ 0 ] = null;
    8.         $this->fn = function( $data ){
    9.             return $data;
    10.         };
    11.     }
    12. }
    13. class Max extends Base{
    14.     public function __construct(){
    15.         parent::__construct();
    16.     }
    17.     // arr 要调整的数组资源 
    18.     // from 根节点的偏移量
    19.     // to 子树的偏移量 
    20.     // fn 函数
    21.     public static function adjust( &$arr, $from, $to, $fn ){
    22.         //$tempValue = $fn( $arr[ $from ] );
    23.       $rootValue = $arr[ $from ];    
    24.         // parent 是根节点，parent * 2是左子树, ( parent * 2 ) + 1是右子树
    25.     // 对于此处来说，收到的只有父节点而已，根据父节点来判断子节点而并不是直接将子节点当参数传输进来
    26.     //echo 'from : '.$from.PHP_EOL;
    27.         for( $parent = $from; $parent * 2 <= $to; $parent = $child ){
    28.             $child = $parent * 2;
    29.             if( $child < $to && $arr[ $child ] < $arr[ $child + 1 ] ){
    30.                $child++;
    31.             }      
    32.           //echo $parent.' : '.$child.PHP_EOL.PHP_EOL;
    33.             // 如果根节点比子节点小，那么交换二者数据
    34.             if( $rootValue < $arr[ $child ] ){
    35.                 $temp = $arr[ $parent ];
    36.                 $arr[ $parent ] = $arr[ $child ];
    37.               $arr[ $child ] = $temp;    
    38.             } else {
    39.                 //echo "避免重复比较".PHP_EOL;
    40.                 break;
    41.             }
    42.         }
    43.     }
    44.     public static function array2max( array $arr ){
    45.     $max = new Max();
    46.     $max->size = count( $arr ); 
    47.         array_unshift( $arr, null );
    48.         //print_r( $arr );exit;
    49.         // 开始循环数组
    50.         for( $i = $max->size; $i > 0; $i-- ){
    51.             // 这个循环就是用来 确定每个节点以及其父节点的
    52.       $parentIndex = floor( $i / 2 ); 
    53.             if( $parentIndex > 0 ){
    54.               //echo $parentIndex.PHP_EOL;
    55.               self::adjust( $arr, $parentIndex, $max->size, $max->fn );    
    56.             }
    57.         }
    58.         $max->element = $arr;
    59.         //print_r( $max->element );
    60.         return $max;
    61.     }
    62.     public function delete(){
    63.         $data = $this->element[ 1 ];
    64.         $this->element[ 1 ] = $this->element[ $this->size ];
    65.         self::adjust( $this->element, 1, $this->size-1, $this->fn );
    66.         unset( $this->element[ $this->size ] );
    67.         $this->size--;
    68.         return $data;
    69.     }
    70.     public function insert( $data ){
    71.         $this->size++;
    72.         $this->element[ $this->size ] = $data;
    73.         for( $i = $this->size; $i > 0; $i-- ){
    74.             $parentIndex = floor( $i / 2 );
    75.             if( $parentIndex > 0 ){
    76.         self::adjust( $this->element, $parentIndex, $this->size, $this->fn );
    77.             }
    78.         }
    79.     }
    80. }
    81. $max = Max::array2max( array( 50, 10, 90, 30, 70, 40, 80, 60, 20 ) );
    82. print_r( $max->element );
    83. $max->insert( 5 );
    84. print_r( $max->element );
    85. $max->delete();
    86. print_r( $max->element );

    实际上，有为青年可能已经研究到了，php的SPL中已经内置了Heap这种数据结构，我就贴个链接，你们感受一下：点击这里