二分ヒープとは
にぶんひーぷ
親の値が子の値以上(最大ヒープ)または以下(最小ヒープ)になるように値を置いた完全二分木。配列で表せ、根を a[0] とすると a[i] の子は a[2i+1] と a[2i+2]。最大値(最小値)の参照が O(1)、追加と取り出しが O(log n) で、優先度付きキューやヒープソートに使われる。
「二分ヒープ」は、1分野の3問の練習問題に出てきます(データ構造とアルゴリズムなど)。
この用語の分野: データ構造とアルゴリズム
二分ヒープの練習問題に挑戦
二分ヒープを、根を a[0] とする配列 a[0], a[1], a[2], … に、上の段から順に左から詰めて格納する。a[4] の子と親はどれか。
- A子は a[9] と a[10]、親は a[1]
- B子は a[8] と a[9]、親は a[2]
- C子は a[9] と a[10]、親は a[2]
解説の中の「二分ヒープ」
ヒープソートは、配列の中に二分ヒープを作り、根の最大値を末尾と交換してヒープを縮めることを繰り返すので、最悪でも O(n log n) で、追加の領域は定数で済みます。
最悪の場合でも計算量が O(n log n) で、作業用の配列などの追加の記憶領域をほとんど使わずに並べ替えられるソー…この性質から、二分ヒープは優先度付きキューの実装によく使われます。
親の値が子の値以上になる最大ヒープを、根を a[0] とする配列で表している。ヒープ 50, 30, 40, 10, …
「二分ヒープ」が出てくる問題(3問)
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。