php堆排序詳解

小云云原創: 2018-03-29 11:35:261942瀏覽

堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種。可以利用陣列的特性快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二元樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在陣列的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

堆的定義

在一個完全二元樹中，任一父結點總是大於或等於（小於或等於）任何一個子節點，則為大頂堆（小頂堆）。

堆的陣列儲存方式

完全二元樹適合採用順序儲存的方式，因此一個陣列可以看成一個完全二元樹。

節點編號：樹根起，從上層到下層，每層從左到右，給所有結點順序編號，能得到一個反映整個二元樹結構的線性序列。

php堆排序詳解

編號特徵：

從一個結點的編號就可推得其雙親，左、右孩子，兄弟等結點的編號。假設編號為i的結點為ki(1≤i≤n)，則有：

　　①若i>1，則ki的雙親編號為i/2；若i=1，則Ki是根結點，無雙親。

　　②若2i≤n，則Ki的左孩子的編號是2i；否則，Ki無左孩子，即Ki必定是葉子。因此完全二元樹中編號i>n/2的結點必定是葉結點。

　　③若2i+1≤n，則Ki的右孩子的編號是2i+1；否則，Ki無右孩子。

註：ki(0≤i≤n)滿足數組下標時,則可能的左右孩子分別為2i+1、2i+2。

堆排序的想法（以大頂堆為例）

利用堆頂記錄的是最大關鍵字這一特性，每一輪取堆頂元素放入有序區，就類似選擇排序每一輪選擇一個最大值放入有序區，可以把堆排序看成是選擇排序的改進。

將初始待排序關鍵字序列(R0,R1,R2....Rn)建構成大頂堆，此堆為初始的無序區；
將堆頂元素R[0]與最後一個元素R[n]交換，此時得到新的無序區(R0,R1,R2,......Rn-1 )和新的有序區(Rn)；
由於交換後新的堆頂R[0]可能違反堆的性質，因此需要對當前無序區(R0, R1,R2,......Rn-1)調整為新堆。

不斷重複此2、3步驟直到有序區的元素個數為n-1，則整個排序過程完成。

演算法分析

php堆排序詳解

篩選演算法

//最難理解的地方

目標：一個所有子樹都為堆的完全二元樹。意思就是這個二元樹只差跟節點不滿足堆的結構。 //很重要，很重要，很重要

如下圖：

clip_php堆排序詳解002

##方法：首先將root和它的左右子樹的根結點進行比較，把最大的元素交換到root節點；然後順著被破壞的路徑一路調整下去，直至葉子結點，就得到新的堆。

clip_php堆排序詳解003

運用：1.在上文提到的堆排序思想，2-3步驟中將無序區調整為堆的時候用到。

2.初始化堆疊

初始化堆疊

從最後一個非葉節點i（i=n/2,n為節點數）開始，將以i為根節點的二元樹透過篩選調整為堆疊。以第一張圖為例，編號順序為8、7、6...1。

從最後一個非葉子節就保證了篩選演算法的正確性，因為篩選演算法的目標是一個所有子樹都為堆的完全二元樹。

php实现堆排序：
<?php
//堆排序，对简单排序的改进
  function swap(array &$arr,$a,$b)
  {
      $temp=$arr[$a];
      $arr[$a]=$arr[$b];
      $arr[$b]=$temp;
  }
  //调整$arr[$start]的关键字，$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆（根节点最大的完全二叉树）
  //注意：这里节点s的左右孩子是 2*s +1 和 2*s+2(数组开始下标为0时)
   function HeapAdjust(array &$arr $start $end)
   {
       $temp= $arr[$start];
       //沿关键字较大的孩子节点向下筛选
       //左右孩子计算 （这里数组的开始下标为0）
       //左边孩子 2*$start+1,右边孩子 2*$start+2
       for ($j=2*$start+1; $j <=$end; $j=2*$j+1) { 
           if ($j !=$end &&$arr[$j] <$arr[$j+1]) {
               $j++;  //转化为右边孩子
           }
           if ($temp >=$arr[$j]) {
               break;  //已经满足大根堆
           }
           //将根节点设置为子节点的较大值
           $arr[$start]=$arr[$j];
           //继续往下
           $start=$j;
       }
       $arr[$start] =$temp;
   }
   function HeapSort(array &$arr)
   {
       $count=count($arr);
       //先将数据结构造成大根堆 （由于是完全二叉树，所以这里用floor($count/2-1),下标小于或等于这个数的节点都是有孩子的节点)
       for ($i=floor($count /2)-1; $i >=0 ; $i--) { 
           HeapAdjust($arr,$i,$count);
       }
       for ($i=$count-1; $i >=0 ; $i--) { 
       //将堆顶元素与最后一个元素交换，获取到最大元素(交换后的最后一个元素)，将最大元素放到数组末尾
           swap($arr,0,$i);
       //经过交换，将最后一个元素（最大元素）脱离大根堆，并将未经排序的新数（$arr[0...$i-1]）重新调整为大根堆
           HeapAdjust($arr,0,$i-1);
       }
   }
   $arr=array(4,1,5,9);
   HeapSort($arr);
   v

php堆排序詳解

堆的陣列儲存方式

堆排序的想法（以大頂堆為例）

篩選演算法

相關文章