Вопрос
Я вроде застрял с моей кучей сортировки здесь в 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);
?>
Я не могу отсортировать массив, есть идеи, что не так?
Решение
siftDown () должен изменить массив, который вы передаете. Поэтому вы должны передать его по ссылке. В противном случае функция будет работать с копией данных.
function siftDown(&$a, $start, $end) {
Другие советы
Я думаю, что это самый простой код для сортировки кучи в php а> р>
Я не эксперт по PHP, но не похоже, что heapify
сделан правильно - как может heapification сводиться к куче вызовов siftDown ...? Последний написан, предполагая, что он имеет дело с массивом, который является кучей (возможно, с одним исключением), тогда как heapify
- это то, что устанавливает инварианты кучи в первую очередь ...
Не связан с StackOverflow