Besoin d'aide avec mon tri de tas
Question
Je suis un peu coincé avec mon genre de tas ici en php:
<?php
function heapSort($a, $count){
$a = heapify($a, $count);
$end = $count - 1;
while ($end > 0){
$temp = $a[$end];
$a[$end] = $a[0] ;
$a[0]= $temp;
$end = $end - 1;
siftDown($a, 0, $end);
}
return $a;
}
function heapify($a,$count){
$start = ($count - 2) / 2;
while ($start >= 0){
$a = siftDown($a, $start, $count-1);
$start = $start - 1;
}
return $a;
}
function siftDown($a, $start, $end){
$root = $start;
while ($root * 2 + 1 <= $end){// While the root has at least one child
$child = $root * 2 + 1; // root*2+1 points to the left child
//If the child has a sibling and the
//child's value is less than its
//sibling's
if ($child + 1 <= $end and $a[$child] < $a[$child + 1])
$child = $child + 1;// then point to the right child instead)
if ($a[$root] < $a[$child]){ // out of max-heap order
list($a[$child],$a[$root]) = array($a[$root],$a[$child]);
$root = $child; // repeat to continue sifting down
// the child now
}
else {
return $a;
}}
return $a;
}
$a = Array(3,1,5,2);
$b = heapSort($a,count($a));
print_r($b);
?>
Je n'arrive pas à trier le tableau, avez-vous une idée de ce qui ne va pas?
La solution
siftDown () est supposé modifier le tableau que vous avez transmis. Par conséquent, vous devez le transmettre par référence. Sinon, la fonction fonctionnera sur une copie des données.
function siftDown(&$a, $start, $end) {
Autres conseils
Je pense que c'est le code le plus simple pour Trier par php
Je ne suis pas un expert en PHP, mais il ne semble pas que heapify
soit bien fait - comment une tasification peut-elle se résumer à un tas d'appels à siftDown ...? Ce dernier est écrit en supposant qu’il s’agit d’un tableau qui EST un tas (avec peut-être une exception), tandis que heapify
est ce qui établit les invariants de tas en premier lieu ...