【SPL標準庫專題(8)】Datastructures：SplHeap & SplMaxHe

chadLi 發布于2019-07-01 12:49 / 722人閱讀

摘要：堆就是為了實現優先隊列而設計的一種數據結構，它是通過構造二叉堆二叉樹的一種實現。根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。二叉堆還常用于排序堆排序。

堆(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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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

摘要：是用來存儲一組對象的，特別是當你需要唯一標識對象的時候。類實現了四個接口?？蓪崿F統計迭代序列化數組式訪問等功能。 PHP SPL SplObjectStorage是用來存儲一組對象的，特別是當你需要唯一標識對象的時候。PHP SPL SplObjectStorage類實現了Countable,Iterator,Serializable,ArrayAccess四個接口?？蓪崿F統計、迭代、...

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