完全二叉樹

創(chuàng)新互聯(lián)建站長(zhǎng)期為1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為潮陽(yáng)企業(yè)提供專業(yè)的成都網(wǎng)站制作、成都做網(wǎng)站，潮陽(yáng)網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

說(shuō)到堆排序，就不能不提完全二叉樹，這些基本概念在網(wǎng)上到處都是，我摘了個(gè)最簡(jiǎn)單的。。

完全二叉樹：除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

我自己總結(jié)認(rèn)為，正是因?yàn)橛邢旅鎯蓚€(gè)特點(diǎn)，

• 只允許最后一層有空缺結(jié)點(diǎn)且空缺在右邊，即葉子結(jié)點(diǎn)只能在層次大的兩層上出現(xiàn)（存儲(chǔ)方式的規(guī)則性）；
• 若i>1，tree的雙親為tree[i div 2]（其父子結(jié)點(diǎn)值的規(guī)律性）；

才使得其進(jìn)行排序非常方便。

堆排序

堆排序(Heapsort)是指利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，大的值一定在堆頂。

堆排序步驟如下：

1、我們將數(shù)據(jù)（49、38、65、97、76、13、27、50）建立一個(gè)數(shù)組$arr；

2、用數(shù)組$arr建立一個(gè)小頂堆（主要步驟，會(huì)在代碼注釋里解釋，下圖是用一個(gè)數(shù)組建立小頂堆的過(guò)程）；

3、將堆的根（最小的元素）與最后一個(gè)葉子交換，并將堆長(zhǎng)度減一，跳到第二步；

4、重復(fù)2-3步，直到堆中只有一個(gè)結(jié)點(diǎn)，排序完成。

堆排序的PHP實(shí)現(xiàn)

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

//將第一次排序抽出來(lái)，因?yàn)樽詈笠淮闻判虿恍枰俳粨Q值了。
buildHeap($arr,$arrSize);

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

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

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

當(dāng)前文章：PHP中堆排序的原理和應(yīng)用-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.rwnh.cn/article24/dcopje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷推廣、用戶體驗(yàn)、網(wǎng)站制作、建站公司、手機(jī)網(wǎng)站建設(shè)、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)