当前位置:首页 > PHP教程 > php高级应用 > 列表

【PHP】堆排序的原理以及实现代码

发布:smiling 来源: PHP粉丝网  添加日期:2020-03-31 18:16:17 浏览: 评论:0 

本篇文章的主要内容是用PHP实现堆排序,具有一定的参考价值,感兴趣的朋友可以了解一下。

1.堆(二叉堆):可以视为一棵完全的二叉树,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素

2.给出某个结点的下标,可以计算出父结点的和孩子结点的下标; parent(i)=floor(i/2) left(i)=2i right=2i+1

3.最大堆和最小堆,最大堆:根结点是最大值,最小堆:根结点是最小值

4.堆排序就是把最大堆堆顶的最大数取出,剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,直到剩余数只有一个结束

5.最大堆调整(维护最大堆,子节点永远小于父结点) ;创建最大堆(把一个数组调整成最大堆的数组);堆排序(创建最大堆,交换,维护最大堆)

  1. maxHeapify (array,index,heapSize) //最大堆调整 
  2.  
  3.     iMax,iLeft,iRight 
  4.  
  5.     while true 
  6.  
  7.         iMax=index;iLeft=2*index+1;iRight=2*index+2 
  8.  
  9.         如果根结点小于左右子树里结点值,就交换一下这两个值 
  10.  
  11.         利用第三方变量,交换下两个值 
  12.  
  13. buildMaxHeap(array) //创建最大堆,把一个数组调整成最大堆的数组 
  14.  
  15.     iParent=floor((size-1)/2) 
  16.  
  17.     for i=iParent;i>=0;i-- 
  18.  
  19.         maxHeapify (array,i,size) 
  20.  
  21. sort(arr) 
  22.  
  23.     buildMaxHeap(array, heapSize);//创建最大堆 
  24.  
  25.     for (int i = heapSize - 1; i > 0; i--) { 
  26.  
  27.         swap(array, 0, i); //交换第一个和最后一个 
  28.  
  29.          maxHeapify(array, 0, i);//维护最大堆,size小了一个  
  30.  
  31. //交换元素 
  32.  
  33. function swap(&$arr,$a,$b){ 
  34.  
  35.         $temp=$arr[$a]; 
  36.  
  37.         $arr[$a]=$arr[$b]; 
  38.  
  39.         $arr[$b]=$temp; 
  40.  
  41. } 
  42.  
  43. //排序的入口函数 
  44.  
  45. function heapSort(&$arr){ 
  46.  
  47.         $heapSize=count($arr); 
  48.  
  49.         buildMaxHeap($arr, $heapSize);//创建最大堆 
  50.  
  51.         for ($i = $heapSize - 1; $i > 0; $i--) { 
  52.  
  53.                 swap($arr,0,$i); //交换第一个和最后一个 
  54.  
  55.                 maxHeapify($arr, 0, $i);//维护最大堆,size小了一个 
  56.  
  57.         }    
  58.  
  59. } 
  60.  
  61. //创建最大堆的函数 
  62.  
  63. function buildMaxHeap(&$arr, $heapSize){ 
  64.  
  65.         $iParent=floor(($heapSize-1)/2);//根据最后一个元素的索引值计算该结点根结点的索引是哪个 
  66.  
  67.         for($i=$iParent;$i>=0;$i--){//这个循环是循环的所有根结点 
  68.  
  69.                 maxHeapify($arr,$i,$heapSize);//维护最大堆 
  70.  
  71.         }    
  72.  
  73. } 
  74.  
  75. //维护最大堆 
  76.  
  77. function maxHeapify(&$arr,$index,$heapSize){ 
  78.  
  79.         $iMax=0;$iLeft=0;$iRight=0; 
  80.  
  81.         while(true){ 
  82.  
  83.                 $iMax=$index; 
  84.  
  85.                 $iLeft=2*$iMax+1; 
  86.  
  87.                 $iRight=2*$iMax+2; 
  88.  
  89.                 if($iLeft<$heapSize && $arr[$iLeft]>$arr[$iMax]){ 
  90.  
  91.                         $iMax=$iLeft; 
  92.  
  93.                 }    
  94.  
  95.                 if($iRight<$heapSize && $arr[$iRight]>$arr[$iMax]){ 
  96.  
  97.                         $iMax=$iRight; 
  98.  
  99.                 }    
  100.  
  101.                 if($iMax!=$index){ 
  102.  
  103.                         swap($arr,$index,$iMax); 
  104.  
  105.                         $index=$iMax; 
  106.  
  107.                 }else{ 
  108.  
  109.                         break; 
  110.  
  111.                 }    
  112.  
  113.         }    
  114.  
  115. } 
  116.  
  117. $arr=array(2,1,3,5,9,6); 
  118.  
  119. heapSort($arr); 
  120.  
  121. var_dump($arr); 

Tags: PHP堆排序原理

分享到: