<?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];
}
- Output for 7.0.0 - 7.0.20, 7.1.0 - 7.1.20, 7.2.6 - 7.2.33, 7.3.16 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30, 8.1.0 - 8.1.31, 8.2.0 - 8.2.27, 8.3.0 - 8.3.16, 8.4.1 - 8.4.3
- array(9) {
[0]=>
int(1)
[1]=>
int(2)
[2]=>
int(3)
[3]=>
int(4)
[4]=>
int(5)
[5]=>
int(6)
[6]=>
int(7)
[7]=>
int(8)
[8]=>
int(9)
}
array(9) {
[0]=>
int(1)
[1]=>
int(2)
[2]=>
int(3)
[3]=>
int(4)
[4]=>
int(5)
[5]=>
int(6)
[6]=>
int(7)
[7]=>
int(8)
[8]=>
int(9)
}
int(9)
preferences:
143.89 ms | 409 KiB | 5 Q