Advertisement
h-collector

Heap sort in php

Dec 18th, 2011
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 0.93 KB | None | 0 0
  1. //http://phpcyborg.blogspot.com/2011/04/heap-sort-in-php.html
  2. <?php
  3.     function build_heap(&$array, $i, $t){
  4.   $tmp_var = $array[$i];    
  5.   $j = $i * 2 + 1;
  6.  
  7.   while ($j <= $t)  {
  8.    if($j < $t)
  9.     if($array[$j] < $array[$j + 1]) {
  10.      $j = $j + 1;
  11.     }
  12.    if($tmp_var < $array[$j]) {
  13.     $array[$i] = $array[$j];
  14.     $i = $j;
  15.     $j = 2 * $i + 1;
  16.    } else {
  17.     $j = $t + 1;
  18.    }
  19.   }
  20.   $array[$i] = $tmp_var;
  21.  }
  22.  
  23.  function heap_sort(&$array) {
  24.   //This will heapify the array
  25.   $init = (count($array) - 1) / 2;
  26.   for($i=$init; $i >= 0; $i--){
  27.    $count = count($array) - 1;
  28.    build_heap($array, $i, $count);
  29.   }
  30.  
  31.   //swaping of nodes
  32.   for ($i = (count($array) - 1); $i >= 1; $i--)  {
  33.    $tmp_var = $array[0];
  34.    $array [0] = $array [$i];
  35.    $array [$i] = $tmp_var;
  36.    build_heap($array, 0, $i - 1);
  37.   }
  38.  }
  39.  
  40. // Demo
  41. $array = array(9,8,7,6,5,4,3,2,1,0,10,1000,0);
  42. heap_sort($array);
  43. print_r($array);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement