ヒープの実装

ウィキペディア小見出し辞書

ヒープの実装

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/03 14:40 UTC 版)

「二分ヒープ」の記事における「ヒープの実装」の解説

古典的な二分木データ構造を使って、二分ヒープ木を構築することは完全に可能である。ただ、要素を追加する時に、次に追加する要素をぶら下げるべき要素を探すのに手間がかかる、という問題がある。素直に実装した二分木では、根元に向かうリンクが存在しないためである。これは「スレッド木」と呼ばれているデータ構造により困難を緩和できる。 スレッド木とは、末端の要素において、子要素への参照として null 等を格納するかわりに、通りがけ順（二分木#行きがけ順、通りがけ順、帰りがけ順探索を参照）における先行要素と後続要素への参照を格納し、探索を容易にした二分木データ構造である。 しかし、より普及しているやり方は、配列に写す方法である。以下のように、ほとんど完全な二分木の要素に番号を付けてみる。まず、根元の要素に 1 という番号を付ける。以下幅優先で順番に番号を振ってゆく（図を参照）。 すると、番号に次のような規則があることがわかる。ある要素に振られた番号を n とすると、 左の子は 2n 右の子は 2n + 1 親は floor(n / 2) （※多くの処理系で、整数除算として単に n / 2 で実装できる） 兄弟（ないし同世代） n + 1, n - 1 この規則性により、ほとんど完全な二分木は、ポインタ用のメモリを必要とせず、（可変長の）配列に、たいへん効率よく詰め込むことができ、また要素を辿ることもできる。これは暗黙のデータ構造の一つの単純な例である。 このやり方は、ヒープソートで特に役に立つ。入力の配列を、ヒープを格納するために再利用し、in-place なソートが実現できるからである。 0 からの番号付けだと、式が少し複雑になるので、1 からの番号付けが一般に使われる。C言語など、配列が 0 始まりの場合には、配列の 0 番目を、「ルートのルート」と言われるような手法のための番兵のデータを置いたり、そのヒープ木の現在の要素数の格納などに流用することがある。二分ヒープ木のマージは、等しいサイズのヒープ2個の場合、Θ(n)だけかかる。マージ処理がよく使われる処理であるならば、二項ヒープのような違うヒープ実装を推奨する。