基于PHP實現(xiàn)堆排序原理及實例詳解

//因為是數(shù)組,下標(biāo)從0開始,所以,下標(biāo)為n根結(jié)點的左子結(jié)點為2n+1,右子結(jié)點為2n+2; 
//初始化值,建立初始堆
$arr=array(49,38,65,97,76,13,27,50);
$arrSize=count($arr);

//將第一次排序抽出來，因為最后一次排序不需要再交換值了。
buildHeap($arr,$arrSize);

for($i=$arrSize-1;$i>0;$i--){
  swap($arr,$i,0);
  $arrSize--;
  buildHeap($arr,$arrSize);  
}

//用數(shù)組建立最小堆
function buildHeap($arr,$arrSize){
  //計算出最開始的下標(biāo)$index,如圖,為數(shù)字"97"所在位置,比較每一個子樹的父結(jié)點和子結(jié)點,將最小值存入父結(jié)點中
  //從$index處對一個樹進行循環(huán)比較,形成最小堆
  for($index=intval($arrSize/2)-1; $index>=0; $index--){
    //如果有左節(jié)點,將其下標(biāo)存進最小值$min
    if($index*2+1$arrSize){
      $min=$index*2+1;
      //如果有右子結(jié)點,比較左右結(jié)點的大小,如果右子結(jié)點更小,將其結(jié)點的下標(biāo)記錄進最小值$min
      if($index*2+2$arrSize){
        if($arr[$index*2+2]$arr[$min]){
          $min=$index*2+2;
        }
      }
      //將子結(jié)點中較小的和父結(jié)點比較,若子結(jié)點較小,與父結(jié)點交換位置,同時更新較小
      if($arr[$min]$arr[$index]){
        swap($arr,$min,$index);
      }  
    }
  }
}

//此函數(shù)用來交換下數(shù)組$arr中下標(biāo)為$one和$another的數(shù)據(jù)
function swap($arr,$one,$another){
  $tmp=$arr[$one];
  $arr[$one]=$arr[$another];
  $arr[$another]=$tmp;
}