【SPL标准库专题(8)】Datastructures：SplHeap & SplMaxHe

chadLi 发布于2019-07-01 12:49 / 709人阅读

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

堆(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();
}

GPU云服务器云服务器标准库调用 python 标准库 jstlsqlelweb标准标签库 php标准库str

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31552.html

【SPL标准库专题(6)】Datastructures：SplStack &amp; SplQueu

摘要：这两个类都是继承自，分别派生自的堆栈模式和队列模式所以放在一起来介绍堆栈类摘要方法重写了父类，固定为堆栈模式，然后此处只需要传或者。这两个类都是继承自SplDoublyLinkedList，分别派生自SplDoublyLinkedList的堆栈模式和队列模式；所以放在一起来介绍；堆栈SplStack showImg(https://segmentfault.com/img/remo...

TigerChain 2019-07-01 12:48 评论0 收藏0
【SPL标准库专题(7)】Datastructures：SplPriorityQueue

摘要：普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头取出。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先取出。优先队列具有最高级先出，的行为特征。普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头取出。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先取出。优先队列具有最高级先出（largest-in，first...

mindwind 2019-07-01 12:49 评论0 收藏0
【SPL标准库专题(10)】Datastructures：SplObjectStorage

摘要：是用来存储一组对象的，特别是当你需要唯一标识对象的时候。类实现了四个接口。可实现统计迭代序列化数组式访问等功能。 PHP SPL SplObjectStorage是用来存储一组对象的，特别是当你需要唯一标识对象的时候。PHP SPL SplObjectStorage类实现了Countable,Iterator,Serializable,ArrayAccess四个接口。可实现统计、迭代、...

ConardLi 2019-07-01 12:50 评论0 收藏0
【SPL标准库专题(9)】Datastructures：SplFixedArray

摘要：主要是处理数组相关的主要功能，与普通不同的是，它是固定长度的，且以数字为键名的数组，优势就是比普通的数组处理更快。类摘要方法导入数组，返回对象把对象数组导出为真正的数组由于是定长数组，所以超过定长就会抛出异常。 SplFixedArray主要是处理数组相关的主要功能，与普通php array不同的是，它是固定长度的，且以数字为键名的数组，优势就是比普通的数组处理更快。类摘要 SplF...

lindroid 2019-07-01 12:49 评论0 收藏0
【SPL标准库专题(5)】Datastructures：SplDoublyLinkedList

摘要：简述双链表是一种重要的线性存储结构，对于双链表中的每个节点，不仅仅存储自己的信息，还要保存前驱和后继节点的地址。简述双链表是一种重要的线性存储结构，对于双链表中的每个节点，不仅仅存储自己的信息，还要保存前驱和后继节点的地址。 showImg(https://segmentfault.com/img/remote/1460000019231932?w=813&h=236); 类摘要 ...

luckyw 2019-07-01 12:48 评论0 收藏0