作为一种可以使用数组实现的数据结构，使用php来模拟优先队列(堆排序)还是比较容易的。下面是我们的实现代码，其中insert使用的是上滤，delete使用的是下滤。我们模拟实现了最小堆和最大堆。
当然，php的spl库提供了类似的数据结构，它们基于c实现，在时间和空间上应该优于我们直接基于php的实现，大家可以参考下: 最小堆：http://php.net/manual/zh/class.splminheap.php 最大堆：http://php.net/manual/zh/class.splmaxheap.php
GitHub源码
<?php
header(
'content-type:text/html;charset=utf-8');
abstract class Heap
{
protected $heap = [
0];
protected $size =
0;
public function __construct(array $dataList = [])
{
foreach (
$dataList as $value) {
$this->size++;
$this->insert(
$value);
}
}
abstract public function insert($value);
abstract public function delete();
public function sort()
{
$result = [];
$size =
$this->size;
for (
$i =
1;
$i <=
$size;
$i++) {
$result[] =
$this->delete();
}
return $result;
}
}
class MinHeap extends Heap
{
public function insert($value)
{
for (
$i =
$this->size; (
$i >
0) && (
$this->heap[floor(
$i/
2)] >
$value);
$i = floor(
$i/
2)) {
$this->heap[
$i] =
$this->heap[floor(
$i/
2)];
}
$this->heap[
$i] =
$value;
}
public function delete()
{
$minValue =
$this->heap[
1];
$lastValue =
$this->heap[
$this->size--];
$child =
1;
for (
$i =
1;
$i*
2 <=
$this->size;
$i =
$child) {
$child =
$i *
2;
$leftIndex =
$child;
$rightIndex =
$child +
1;
if ((
$child !=
$this->size) && (
$this->heap[
$leftIndex] >
$this->heap[
$rightIndex])) {
$child++;
}
if (
$lastValue >
$this->heap[
$child]) {
$this->heap[
$i] =
$this->heap[
$child];
}
else {
break;
}
}
$this->heap[
$i] =
$lastValue;
return $minValue;
}
}
class MaxHeap extends Heap
{
public function insert($value)
{
for (
$i =
$this->size; (floor(
$i/
2) >
0) && (
$this->heap[floor(
$i/
2)] <
$value);
$i = floor(
$i/
2)) {
$this->heap[
$i] =
$this->heap[floor(
$i/
2)];
}
$this->heap[
$i] =
$value;
}
public function delete()
{
$maxValue =
$this->heap[
1];
$lastValue =
$this->heap[
$this->size--];
$child =
1;
for (
$i =
1;
$i *
2 <=
$this->size;
$i =
$child) {
$child =
$i *
2;
$leftIndex =
$child;
$rightIndex =
$child +
1;
if ((
$child !=
$this->size) && (
$this->heap[
$leftIndex] <
$this->heap[
$rightIndex])) {
$child++;
}
if (
$this->heap[
$child] >
$lastValue) {
$this->heap[
$i] =
$this->heap[
$child];
}
else {
break;
}
}
$this->heap[
$i] =
$lastValue;
return $maxValue;
}
}
class Test
{
public function run()
{
$testData = [
33,
4,
3,
2,
5,
6,
9,
10,
32,
23,
45,
11,
25];
$minHeap =
new MinHeap(
$testData);
$maxHeap =
new MaxHeap(
$testData);
var_dump(
$minHeap->sort());
var_dump(
$maxHeap->sort());
}
}
$test =
new Test();
$test->run();
