サンプル・プログラム
| dt03-44.php | PHPサンプル・プログラム本体（PHP8対応） |
| pahooDataStructure.php | PHPでデータ構造を実現する各種クラス（PHP8対応） |
ヒープ
- 子要素が親要素より常に大きいか等しい
- 子要素は2つで、右要素が左要素より常に大きいか等しい（2分木）
ここでは、11番目の要素として9を追加することを考える。
さらに上の親ノード（2番目）とも比較しながら、必要があれば入れ換えていく。
この一連の操作を最小ヒープと呼ぶことにする。
ヒープソート
この性質を使って要素の並び替えを行うことができる。
この作業を、ヒープの要素がなくなるまで続けることで、別の配列に要素が昇順に並べ替えされて格納されることになる。
PHPによるヒープ
1740: // pahooHeap クラス ========================================================
1741: class pahooHeap { //ヒープ
1742: public $heap; //ヒープ配列
1743: public $cnt; //要素の個数
1744: public $error, $errmsg; //エラーフラグ，エラーメッセージ（未使用）
1745:
1746: /**
1747: * コンストラクタ
1748: * @param mixed $key 格納するキー
1749: * @param mixed $item 格納する要素
1750: * @param pahooHeap $paret 親ノード／NULL：自らが親ノード
1751: * @param pahooHeap $left 親ノードの左ならTRUE、右ならFALSE
1752: * @return なし
1753: */
1754: function __construct($key=NULL, $item=NULL, $parent=NULL, $left=NULL) {
1755: $this->heap = array();
1756: $this->cnt = 0;
1757: $this->error = FALSE;
1758: $this->errmsg = '';
1759: }
ヒープ構造はクラスの配列変数 $heap を使って実装する。これをヒープ配列と呼ぶことにする。
1806: /**
1807: * ヒープに要素を1つ追加する
1808: * @param mixed $key 格納するキー
1809: * @param mixed $item 格納する要素
1810: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1811: * $a > $b なら TRUEを返す
1812: * @return なし
1813: */
1814: function insert($key, $item, $cmp=NULL) {
1815: $this->heap[$this->cnt]['key'] = $key;
1816: $this->heap[$this->cnt]['item'] = $item;
1817:
1818: //ヒープの再構築
1819: $this->build_min_heap($this->heap, $cmp);
1820:
1821: $this->cnt++;
1822: }
1761: /**
1762: * 最小ヒープ処理
1763: * @param array $arr ヒープ配列
1764: * @param int $i 親要素の要素番号
1765: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1766: * $a > $b なら TRUEを返す
1767: * @return なし
1768: */
1769: function min_heapify(&$arr, $i, $cmp=NULL) {
1770: $left = 2 * $i + 1;
1771: $right = $left + 1;
1772: $len = count($arr);
1773: $smallest = $i;
1774:
1775: //左の子要素と親要素を比べる
1776: if (($left < $len) && ((($cmp != NULL) && $cmp($arr[$left]['key'], $arr[$i]['key'])) || ($arr[$left]['key'] < $arr[$i]['key']))) {
1777: $smallest = $left;
1778: }
1779: //右の子要素と親要素を比べる
1780: if (($right < $len) && ((($cmp != NULL) && $cmp($arr[$right]['key'], $arr[$smallest]['key'])) || ($arr[$right]['key'] < $arr[$smallest]['key']))) {
1781: $smallest = $right;
1782: }
1783: //必要なら入れ換え
1784: if ($smallest != $i) {
1785: list($arr[$i], $arr[$smallest]) = array($arr[$smallest], $arr[$i]);
1786: //次の要素について再帰処理
1787: $this->min_heapify($arr, $smallest);
1788: }
1789: }
1790:
1791: /**
1792: * ヒープの再構築
1793: * @param array $arr ヒープ配列
1794: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1795: * $a > $b なら TRUEを返す
1796: * @return なし
1797: */
1798: function build_min_heap(&$arr, $cmp=NULL) {
1799: $i = floor($this->cnt / 2);
1800: while ($i >= 0) {
1801: $this->min_heapify($arr, $i);
1802: $i--;
1803: }
1804: }
1824: /**
1825: * ヒープの最小値を取り出す
1826: * @param なし
1827: * @return mixed 最小値の値／NULL：ヒットせず
1828: */
1829: function min() {
1830: return $this->heap[0]['item'];
1831: }
1833: /**
1834: * ヒープから要素を1つ削除する
1835: * @param なし
1836: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1837: * $a > $b なら TRUEを返す
1838: * @return bool TRUE：削除成功／FALSE：失敗（一致するキーがない）
1839: */
1840: function delete($cmp=NULL) {
1841: $n = $this->cnt;
1842:
1843: //最後の葉をルートにコピーし、最後の葉を取り除く
1844: $this->heap[0] = array_pop($this->heap);
1845: $this->cnt--;
1846:
1847: //ヒープの再構築
1848: $this->build_min_heap($this->heap, $cmp);
1849:
1850: return NULL;
1851: }
PHPによるヒープソート
1896: /**
1897: * ヒープソート（昇順）
1898: * @param なし
1899: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1900: * $a > $b なら TRUEを返す
1901: * @return なし
1902: */
1903: function heap_sort($cmp=NULL) {
1904: $sorted = array();
1905: $arr = $this->heap;
1906:
1907: while (count($arr) > 0) {
1908: list($arr[0], $arr[count($arr) - 1]) = array($arr[count($arr) - 1], $arr[0]);
1909: $sorted[] = array_pop($arr);
1910: $this->min_heapify($arr, 0);
1911: }
1912:
1913: return $sorted;
1914: }
PHPによるサンプル・プログラム
また、PHP5.3以降では、基本モジュールとして用意されている SplMinHeapクラスを使うことで最小ヒープを扱うことができる。
2分木構造にすることで、上図のように1次元配列に対応させることができるので、多くの言語で実装が可能であり、プログラムが複雑になることがない。
また、後述するように、並べ替えの計算量を少なくすることができる（ヒープソート）。
なお、OSが用意するヒープ領域（ヒープメモリ）はデータ構造とは何の関係もない。単にヒープと呼ぶ場合、どちらを指しているのか混乱しないようにしよう。