サンプル・プログラム
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によるサンプル・プログラム
0014: // メイン・プログラム ======================================================
0015: $bstree = new pahooBStree(); //二分探索木を用意
0016: $min = 1; //最小値
0017: $max = 10000; //最大値
0018: $loop = 20; //ループ回数
0019:
0020: //要素追加
0021: printf("\n要素追加‥‥");
0022: for ($i = 0; $i < $loop; $i++) {
0023: $k = mt_rand($min, $max); //キー
0024: $item = 'hoge' . $k; //要素
0025: $bstree->insert($k, $item); //キー、要素を追加
0026: if ($i == ($loop / 2)) $key = $k; //探索対象キー
0027: if ($i != 0) printf(", ");
0028: printf("%d:%s", $k, $item);
0029: }
0030:
0031: //一覧
0032: printf("\n\n●一覧");
0033: $cnt = $bstree->count();
0034: printf(" %d個\n", $cnt);
0035: printf("%s\n", $bstree->list());
0036:
0037: //二分探索
0038: printf("\n●二分探索\n");
0039: $item = $bstree->search($key);
0040: printf("%d:%s", $key, $item);
0041:
0042: //削除
0043: printf("\n\n●削除");
0044: $bstree->delete($key);
0045: $cnt = $bstree->count();
0046: printf(" %d個\n", $cnt);
0047: printf("%s\n", $bstree->list());
0048:
0049: $bstree = NULL;
0050:
0051: /*
0052: ** バージョンアップ履歴 ===================================================
0053: *
0054: * @version 1.0 2018/07/24
0055: */
0056: ?>
0057:
また、PHP5.3以降では、基本モジュールとして用意されている SplMinHeapクラスを使うことで最小ヒープを扱うことができる。
2分木構造にすることで、上図のように1次元配列に対応させることができるので、多くの言語で実装が可能であり、プログラムが複雑になることがない。
また、後述するように、並べ替えの計算量を少なくすることができる(ヒープソート)。
なお、OSが用意するヒープ領域(ヒープメモリ)はデータ構造とは何の関係もない。単にヒープと呼ぶ場合、どちらを指しているのか混乱しないようにしよう。