abstract class HeapSort{
protected $count;
protected $data;
public function __construct(array $data)
{
$this->count = count($data);
$this->data = $data;
}
public function run()
{
$this->createHeap();
while ($this->count > 0) {
$this->swap($this->data[0], $this->data[--$this->count]);
$this->buildHeap($this->data, 0, $this->count);
}
return $this->data;
}
public function createHeap()
{
$i = floor($this->count / 2) + 1;
while ($i--) {
$this->buildHeap($this->data, $i, $this->count);
}
}
public function swap(&$left, &$right)
{
list($left, $right) = array ($right, $left);
}
abstract public function buildHeap(array &$data, $i, $count);
}
class HeapMaxSort extends HeapSort
{
public function buildHeap(array &$data, $i, $count)
{
if (false === $i < $count) {
return;
}
$right = ($left = 2 * $i + 1) + 1;
$max = $i;
if ($left < $count && $data[$i] < $data[$left]) {
$max = $left;
}
if ($right < $count && $data[$max] < $data[$right]) {
$max = $right;
}
if ($max !== $i && $max < $count) {
$this->swap($data[$i], $data[$max]);
$this->buildHeap($data, $max, $count);
}
}
}
class HeapMinSort extends HeapSort{
public function buildHeap(array &$data,$i,$count){
if (false === $i < $count) {
return;
}
$right = ($left = 2 * $i + 1) + 1;
$min = $i;
if($left < $count && $data[$i] > $data[$left]){
$min = $left;
}
if($right < $count && $data[$min] > $data[$right]){
$min = $right;
};
if($min < $count && $min != $i){
$this->swap($data[$i], $data[$min]);
$this->buildHeap($data, $min, $count);
}
}
}
$array = array (4, 21, 41, 2, 53, 1, 213, 31, 21, 423, 56);
$result = (new HeapMinSort($array))->run();
$result1 = (new HeapMaxSort($array))->run();
print_r($result);
print_r($result1);
引用自 https://github.com/PuShaoWei/arithmetic-php，在这个基础上重构了一个从大到小的排序