堆排序：什么是堆?什么是最大堆?二叉堆是什么？堆排序算法是怎么樣的？PHP如何實現堆排序？

2019-11-08 00:45:04

字體：大中小

來源：轉載

供稿：網友

本文標簽： 堆排序phpphp算法堆排序算法二叉堆數據結構REST 服務器

什么是堆

這里的堆(二叉堆),指得不是堆棧的那個堆,而是一種數據結構。

堆可以視為一棵完全的二叉樹,完全二叉樹的一個“優秀”的性質是,除了最底層之外,每一層都是滿的,這使得堆可以利用數組來表示,每一個結點對應數組中的一個元素.

數組與堆之間的關系

二叉堆一般分為兩種：最大堆和最小堆。

什么是最大堆

堆中每個父節點的元素值都大于等于其孩子結點（如果存在）,這樣的堆就是一個最大堆

因此,最大堆中的最大元素值出現在根結點(堆頂)

節點與數組索引關系

對于給定的某個結點的下標i，可以很容易的計算出這個結點的父結點、孩子結點的下標，而且計算公式很漂亮很簡約

第二塊,怎么將堆調整為最大堆,這部分是重點

整個過程如下圖所示

在4,14,7這個小堆里邊,父節點4小于左孩子14,所以兩者交換

在4,2,8這個小堆里邊,父節點4小于右孩子8,所以兩者交換

上圖展示了一趟調整的過程,這個過程遞歸實現,直到調整為最大堆為止

第三塊,堆排序介紹

堆排序就是把堆頂的最大數取出,

將剩余的堆繼續調整為最大堆,具體過程在第二塊有介紹,以遞歸實現

剩余部分調整為最大堆后,再次將堆頂的最大數取出,再將剩余部分調整為最大堆,這個過程持續到剩余數只有一個時結束

下邊三張圖詳細描述了整個過程

具體PHP實現：

/**

* 使用異或交換2個值，原理：一個值經過同一個值的2次異或后，原值不變

* @param int $a

* @param int $b

*/

function swap(&$a,&$b){

$a = $a^$b;

$b = $a^$b;

$a = $a^$b;

}

/**

* 整理當前樹節點（$n），臨界點$last之后為已排序好的元素

* @param int $n

* @param int $last

* @param array $arr

*

*/

function adjustNode($n,$last,&$arr){

$l = $n<<1; // 左孩子

if( !isset($arr[$l])||$l>$last){

return ;

}

$r = $l+1; // 右孩子

// 如果右孩子比左孩子大，則讓父節點與右孩子比

if( $r<=$last&&$arr[$r]>$arr[$l] ){

$l = $r;

}

// 如果其中子節點$l比父節點$n大，則與父節點$n交換

if( $arr[$l]>$arr[$n] ){

swap($arr[$l],$arr[$n]);

// 交換之后，父節點($n)的值可能還小于原子節點($l)的子節點的值，所以還需對原子節點($l)的子節點進行調整，用遞歸實現

adjustNode($l, $last,$arr);

}

/**

* 堆排序（最大堆）

* @param array $arr

*/

function heapSort(&$arr){

// 最后一個蒜素位

$last = count($arr);

// 堆排序中常忽略$arr[0]

array_unshift($arr, 0);

// 最后一個非葉子節點

$i = $last>>1;

// 整理成最大堆，最大的數放到最頂，并將最大數和堆尾交換，并在之后的計算中，忽略數組最后端的最大數(last)，直到堆頂（last=堆頂）

while(true){

adjustNode($i, $last,$arr);

if( $i>1 ){

// 移動節點指針，遍歷所有節點

$i--;

}

else{

// 臨界點$last=1，即所有排序完成

if( $last==1 ){

break;

}

swap($arr[$last],$arr[1]);

$last--;

}

// 彈出第一個元素

array_shift($arr);

}

寫在最后：FOR Freedom 看看外邊的世界，以及IT這一行，少不了去Google查資料，最后，安利一個V——PN代理。一枝紅杏加速器，去Google查資料是絕對首選，連接速度快，使用也方便。我買的是99￥一年的，通過這個鏈接（http://my.yizhihongxing.com/aff.php?aff=2509）注冊后輸上會員中心得優惠碼，平攤下來，每月才7塊錢，特實惠。

本文標簽： 堆排序phpphp算法堆排序算法二叉堆數據結構REST 服務器

轉自 SUN'S BLOG - 專注互聯網知識，分享互聯網精神！

原文地址：《堆排序：什么是堆?什么是最大堆?二叉堆是什么？堆排序算法是怎么樣的？PHP如何實現堆排序？》

相關閱讀:《我是 G 粉，一直關注 Google，最近 Google 有一些小動作，可能很多人不太了解》

相關閱讀:《機器學習引領認知領域的技術創新，那么SaaS行業會被機器學習如何改變？》

相關閱讀:《VPS 教程系列：Dnsmasq + DNSCrypt + SNI PRoxy 順暢訪問 Google 配置教程》

相關閱讀: 對程序員有用：2017最新能上Google的hosts文件下載及總結網友遇到的各種hosts問題解決方法及配置詳解

相關閱讀:《Aaron Swartz – 互聯網天才開掛的人生歷程：每時每刻都問自己，現在這世界有什么最重要的事是我能參與去做的？》相關閱讀:《網站環境apache + php + MySQL 的XAMPP，如何實現一個服務器上配置多個網站？》

相關閱讀:《什么是工程師文化？各位工程師是為什么活的？作為一個IT或互聯網公司為什么要工程師文

相關閱讀: 《win10永久激活教程以及如何查看windows系統是不是永久激活？》

相關BLOG：SUN’S BLOG- 專注互聯網知識，分享互聯網精神！去看看：www.whosmall.com

原文地址：http://whosmall.com/?post=244