<?php
$arr = [1,2,3,4,5,6,7,8,9];
heapsort($arr);
var_dump($arr);
$arr = [9,8,7,6,5,4,3,2,1];
heapsort($arr);
var_dump($arr);
$arr = [0,1,2,3,4,5,6,7,8,9,10,11,12,13];
var_dump(big5($arr));
function big5($arr) {
$heapsize = count($arr);
for ($i = intval($heapsize - 2) / 2; $i >= 0; $i--) {
heapify($arr, $i, $heapsize);
}
for ($i = 0; $i < 5; $i++) {
heapify($arr, $i, $heapsize);
}
return $arr[4];
}
function heapsort(&$arr) {
$heapsize = count($arr);
// build heap
for ($i = intval(($heapsize - 2) / 2); $i >= 0; $i--) {
heapify($arr, $i, $heapsize);
}
// heap sort
for ($heapsize = $heapsize - 1; $heapsize > 0; $heapsize--) {
swap($arr[0], $arr[$heapsize]);
heapify($arr, 0, $heapsize);
}
}
function heapify(&$arr, $i, $heapsize) {
while (true) {
$l = 2 * $i + 1;
$r = 2 * $i + 2;
$largest = $i;
if ($l < $heapsize && $arr[$largest] < $arr[$l]) {
$largest = $l;
}
if ($r < $heapsize && $arr[$largest] < $arr[$r]) {
$largest = $r;
}
if ($largest == $i) {
break;
}
swap($arr[$i], $arr[$largest]);
$i = $largest;
}
}
function heapify_recursively(&$arr, $i, $heapsize) {
$l = 2 * $i + 1;
$r = 2 * $i + 2;
$largest = $i;
if ($l < $heapsize && $arr[$largest] < $arr[$l]) {
$largest = $l;
}
if ($r < $heapsize && $arr[$largest] < $arr[$r]) {
$largest = $r;
}
if ($largest != $i) {
swap($arr[$i], $arr[$largest]);
heapify($arr, $largest, $heapsize);
}
}
function swap(&$a, &$b) {
list($a, $b) = [$b, $a];
}
preferences:
32.45 ms | 402 KiB | 5 Q