堆原理)

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

extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。 注意，因为是堆实现，所以rewind方法是一个no-op没有什作用的操作，因为头指针始终指向堆顶，即current始终等于top，不像List只是游走指针，出队是会删除堆元素的，extract=current + next（current出队，从堆中删除）—- 类似于pop和shift

  • 节点与它的父节点和子节点在数组中的位置关系：
    • 公式：
      • parent(index) = floor((index - 1)/2)
      • left(index) = 2index + 1
      • right(index) = 2index + 2

如：[ 10, 14, 25, 33, 81, 82, 99 ]。元素个数为7 so下面索引<=6才有子节点，所以 33, 81, 82, 99 无子节点

Node index Parent index Left child Right child
10 0 -1(不是有效索引so无父节点) 1 2
14 1 0 3 4
25 2 0 5 6
33 3 1 7 8
81 4 1 9 10
82 5 2 11 12
99 6 2 13 14

SplHeap-堆 - 图1

方法

  1. <?php
  2. abstract SplHeap implements Iterator , Countable {
  3.     /* 方法 */
  4.     public __construct ( void )
  5.     abstract protected compare ( mixed $value1 , mixed $value2 ) : int   //比较元素，以便在筛选时将它们正确地放在堆中，如果value1大于value2则为正整数，如果相等则为0，否则为负整数
  6.     public count ( void ) : int    //返回元素的个数 Countable 
  7.     public current ( void ) : mixed    //返回当前记录节点索引的值  超出范围返回空 Iterator
  8.     public extract ( void ) : mixed    //从堆顶部提取节点并进行筛选
  9.     public insert ( mixed $value ) : void    //通过筛选将一个元素插入堆中
  10.     public isCorrupted ( void ) : bool    //判断堆是否处于损坏状态
  11.     public isEmpty ( void ) : bool    //检查堆是否为空
  12.     public key ( void ) : mixed    //返回当前节点索引 Iterator
  13.     public next ( void ) : void    //移动到下一个节点 Iterator
  14.     public recoverFromCorruption ( void ) : void    //从损坏的状态恢复并允许堆上的进一步操作
  15.     public rewind ( void ) : void    //将指针指向迭代开始处 Iterator
  16.     public top ( void ) : mixed    //返回堆顶部的节点
  17.     public valid ( void ) : bool    //检查堆是否还有节点    Iterator
  18. }