PHP 的堆結構：SplMaxHeap vs SplMinHeap 使用指南

更新於 分類於 閱讀次數：

在資料處理上常常會需要取得資料的最大值，但每次都用陣列一次一次找難免費時費力，

在 Leetcode 解題過程中發現 PHP 有對應程式庫能解決此問題，

便想藉這次機會整理相關使用方式順便釐清一遍自己的思路。

基礎概念

Heap，堆積，是一種二元樹狀的資料結構，其中又可分為 最大堆(MaxHeap) 和 最小堆(MinHeap)，

最大堆(MaxHeap) ：根節點(root)始終為最大數值，子節點永遠小於父節點

最小堆(MinHeap)：根節點(root)始終為最小數值，子節點永遠大於父節點

強大的PHP有實作這兩種Heap的函數功能，

MaxHeap / MinHeap 除了最後結果是 最大值 / 最小值外 其餘函數 皆 相同，

以下以 MaxHeap 功能分類做整理。

函數功能

列出實作上會使用的功能參考，

初始宣告

1
$max_heap = new SplMaxHeap();

插入資料：insert()

1
2
3
$max_heap->insert(2);
$max_heap->insert(4);
$max_heap->insert(6);

計算資料數：count()

1
2
$now_count = $max_heap->count();
// $now_count = 3

取得所在位置：current()

1
2
3
$max_heap->rewind(); // 初始化指標，返回最上層
$now_position = $max_heap->current(); // 回傳 6
-> 少了呼叫指標步驟會回傳 NULL

取最大值：top()

1
$curr_max = $max_heap->top(); // 回傳 6

取最大值並移除：extract()

1
2
$curr_max = $max_heap->extract(); // 回傳 6 並 移除資料
-> 若 Heap 中沒資料呼叫會返回錯誤

判斷資料存在：isEmpty()

1
$curr_status = $max_heap->isEmpty(); // 不為空 返回 false

移動資料指針：next()

1
2
$max_heap->next();
$now_position = $max_heap->current(); // 回傳 4

能熟練掌握以上方法，那 SplMaxHeap 操作上就不會有太大問題了！

剩下就是需判斷專案何時該使用此功能的情況了。

應用場景

各類排行榜

每次插入資料 Heap 都會自動變更最大值，能更快速取得數組的排序。

以下就常見的取得最大值方式做 效能比較

功能 時間複雜度 空間複雜度 應用
max() O(n) O(1) 取得當下資料最大值做法
sort() O(n log n) O(n) 需排序資料陣列才會採用
SplMaxHeap O(n log n) O(n) 頻繁取得最大值效能較佳

筆者有在 Leetcode 題目看過不少適用此方法的案例，

實務上反而沒什麼用到，畢竟是比較偏效能優化上的方法，

期許未來接觸到的專案能有使用到的機會吧！

資料參考來源

PHP: Hypertext Preprocessor