1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| <?php /** * */ class HeapSort { public function __construct(&$arr) { $arr_length = count($arr)-1; $this->HeapMaxSort($arr,$arr_length); } private function HeapMaxSort(&$arr,$arr_length) {; $this->BuildMaxHeap($arr,$arr_length); for($i = $arr_length;$i >= 0; $i--) { $this->swap($arr,$i,0); $arr_length--; $this->MaxHeapify($arr,0,$arr_length); } } private function BuildMaxHeap(&$arr,$arr_length) { $count = count($arr)-1; for ($i = floor($count/2); $i >=0; $i--) { $this->MaxHeapify($arr,$i,$arr_length); } }
public function MaxHeapify(&$arr,$i,$arr_length) { $left = $this->left($i); $right = $this->right($i); if($left <= $arr_length && $arr[$left] >= $arr[$i]) { $this->swap($arr,$i,$left); $largest = $left; } else { $largest = $i; } if ($right <= $arr_length && $arr[$right] >= $arr[$largest]) { $this->swap($arr,$largest,$right); $largest = $right; } if ($largest != $i) { $this->MaxHeapify($arr,$largest); } } public function swap(&$arr,$exist,$largest) { $temp = $arr[$exist]; $arr[$exist] = $arr[$largest]; $arr[$largest] = $temp; } private function left($i) { return 2*$i+1; }
private function right($i) { return 2*$i+2; }
} $array = array(5,2,3,1,4,6); $Heap_Model = new HeapSort($array); var_dump($array);
|