<?php

class HeapSort{

    const HEAP_DESC = 1;//降序
    const HEAP_ASC = 2;//升序

    /**
     * 堆排序
     * @param $array 一维数组
     * @param int $sort 排序方式 1 降序 2 升序
     * @param int $top topk值
     * @return mixed
     * @author diyinjie
     */
    static function heap($array,$sort=self::HEAP_DESC,$top=0){
        $size = count($array);
        if(!$size){
            return $array;
        }
        $top=$top?:$size;
        $i = $size;
        for ($i;$i>0;$i--){
            if ($i!=$size){
                self::swap($array,$i,0);//将第一次排序抽出来，因为最后一次排序不需要再交换值了
            }
            if (($size-$i)>($top-1)){
                break;
            }
            if ($sort==self::HEAP_DESC){
                self::heapSort($array,$i);
            }else{
                self::heapAsort($array,$i);
            }

        }
        return $array;
    }

    //用数组建立最小堆 降序
    static function heapSort(&$arr,$arrSize){
        //计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中
        //从$index处对一个树进行循环比较,形成最小堆
        for($index=intval($arrSize/2)-1; $index>=0; $index--){
            //如果有左节点,将其下标存进最小值$min
            if($index*2+1<$arrSize){
                $min=$index*2+1;
                //如果有右子结点,比较左右结点的大小,如果右子结点更小,将其结点的下标记录进最小值$min
                if($index*2+2<$arrSize){
                    if($arr[$index*2+2]<$arr[$min]){
                        $min=$index*2+2;
                    }
                }
                //将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小
                if($arr[$min]<$arr[$index]){
                    self::swap($arr,$min,$index);
                }
            }
        }
    }

    //用数组建立最大堆 升序
    static function heapAsort(&$arr,$arrSize){
        //计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最大值存入父结点中
        //从$index处对一个树进行循环比较,形成最大堆
        for($index=intval($arrSize/2)-1; $index>=0; $index--){
            //如果有左节点,将其下标存进最大值$max
            if($index*2+1<$arrSize){
                $max=$index*2+1;
                //如果有右子结点,比较左右结点的大小,如果右子结点更小,将其结点的下标记录进最大值$max
                if($index*2+2<$arrSize){
                    if($arr[$index*2+2]>$arr[$max]){
                        $max=$index*2+2;
                    }
                }
                //将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小
                if($arr[$max]>$arr[$index]){
                    self::swap($arr,$max,$index);
                }
            }
        }
    }

    //此函数用来交换下数组$arr中下标为$one和$another的数据
    static function swap(&$arr,$one,$another){
        $tmp=$arr[$one];
        $arr[$one]=$arr[$another];
        $arr[$another]=$tmp;
    }
}
?>