SPL标准库专题8DatastructuresSplHeap-SplMaxHeap-SplMinHeap

堆 (Heap) 就是为了实现优先队列而设计的一种数据结构，它是通过构造二叉堆 (二叉树的一种) 实现。根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。二叉堆还常用于排序(堆排序)。

类摘要

abstract SplHeap implements Iterator , Countable {
  /* 方法 */
public __construct (void)
abstract protected int compare (mixed $value1 , mixed $value2)
public int count (void)
public mixed current (void)
public mixed extract (void)
public void insert (mixed $value)
public bool isEmpty (void)
public mixed key (void)
public void next (void)
public void recoverFromCorruption (void)
public void rewind (void)
public mixed top (void)
public bool valid (void)
}

从上面可以看到由于类中包含一个 compare 的抽象方法，所以该类必须为抽象类（不可实例化，只能被继承使用）；

最小堆和最大堆其实就是对 compare 该抽象方法的一个算法的两种呈现； 也可以自己写一个类继承 SplHeap 按自己的方式来做排序；

Example

自定义排序堆

class MySimpleHeap extends SplHeap
{//compare()方法用来比较两个元素的大小，决定他们在堆中的位置
  public function  compare($value1, $value2) {return ($value2 - $value1);
  }
}
$obj = new MySimpleHeap();

$obj->insert(4);
$obj->insert(8);
$obj->insert(1);
$obj->insert(0);

echo $obj->top();  //8

foreach($obj as $number) {
  echo $number;
  echo PHP_EOL;
}

最大堆与最小堆

$heap = new SplMaxHeap();
$heap->insert(100);
$heap->insert(80);
$heap->insert(88);
$heap->insert(70);
$heap->insert(810);
$heap->insert(800);

// 最大堆，从大到小排序
$heap->rewind();
while($heap->valid()){echo $heap->key(),'=>',$heap->current(),PHP_EOL;
  $heap->next();}