ヒープ

最小値または最大値を取り出しやすい
ヒープ
ヒープ
ヒープ(heap)とは、子要素が親要素より常に大きいか等しい(または常に小さいか等しい)という構造をもつツリー構造である。格納しているデータ構造の中から最小値や最大値をすぐに探し出すことができる特長がある。
2分木構造にすることで、上図のように1次元配列に対応させることができるので、多くの言語で実装が可能であり、プログラムが複雑になることがない。
また、後述するように、並べ替えの計算量を少なくすることができる(ヒープソート)。

なお、OSが用意するヒープ領域(ヒープメモリ)はデータ構造とは何の関係もない。単にヒープと呼ぶ場合、どちらを指しているのか混乱しないようにしよう。

目次

サンプル・プログラム

圧縮ファイルの内容
dt03-44.phpPHPサンプル・プログラム本体(PHP8対応)
pahooDataStructure.phpPHPでデータ構造を実現する各種クラス(PHP8対応)

ヒープ

ヒープ
ヒープ
ここでは、
  • 子要素が親要素より常に大きいか等しい
  • 子要素は2つで、右要素が左要素より常に大きいか等しい(2分木)
という条件のヒープを紹介する。2番目の条件はヒープの必須要件ではない。
要素の追加(1) - ヒープ
要素の追加(1)
ヒープで要素を追加するときは、常に、一番最後の葉の部分に追加する。
ここでは、11番目の要素として9を追加することを考える。
要素の追加(2) - ヒープ
要素の追加(2)
要素を追加後、左要素(9番目)と比較すると、大小が逆転している。前述のように必須要件ではないものの、ヒープ構造を保つために左右を入れ換える必要がある。
要素の追加(3) - ヒープ
要素の追加(3)
次に――これはヒープ構造の必須要件であるが――子要素(10番目)と親要素(5番目)の大小が逆転しているため、親子を入れ換える必要がある。
さらに上の親ノード(2番目)とも比較しながら、必要があれば入れ換えていく。
この一連の操作を最小ヒープと呼ぶことにする。

ヒープソート

ヒープソート
ヒープソート
ヒープでは、その定義から、ルートの要素が最小値である。
この性質を使って要素の並び替えを行うことができる。
ヒープソート(1)
ヒープソート(1)
まず、ルートの要素と最後の葉の要素を入れ換える。
ヒープソート(2)
ヒープソート(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: }

PHPのヒープ・クラス pahooHeap最小ヒープを実装している。
ヒープ構造はクラスの配列変数 $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: }

ヒープへ要素を1つ追加するメソッド insert は前述の手順にしたがい、一番最後の葉の部分に追加する。
次に、メソッド build_min_heap を使ってヒープの要素の順序を整える。

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: }

メソッド build_min_heap および min_heapify の動作は、前述の定義をそのまま実装した。

1824: /**
1825:  * ヒープの最小値を取り出す
1826:  * @param   なし
1827:  * @return  mixed 最小値の値/NULL:ヒットせず
1828: */
1829: function min() {
1830:     return $this->heap[0]['item'];
1831: }

ヒープの最小値を取り出すメソッド min は、ヒープの定義から、ヒープ配列の最初の要素を取り出せばよい。

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: }

ヒープから要素を1つ削除する処理は、常に最小値を削除することになる。メソッド delete は、まず、最後の葉をルートにコピーし、最後の葉を取り除く。そのあと、要素追加の時と同様、ヒープの再構築を行う。

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のヒープソート・メソッド heap_sort は、前述の定義をそのまま実装した。

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: 

これまで解説したメソッドの動作を見るサンプル・プログラムが "dt03-42-01.php" である。

また、PHP5.3以降では、基本モジュールとして用意されている SplMinHeapクラスを使うことで最小ヒープを扱うことができる。
(この項おわり)
header