Binary Heap
Operations
$ \mathtt{new}()
空のヒープを作成する
時間計算量$ \Theta(1)/ 空間計算量$ \Theta(1)
$ \mathtt{build}(x_1, x_2, \dots, x_n)
要素$ x_1, x_2, \dots, x_nからなるヒープを作成する
時間計算量$ \Theta(n)/ 空間計算量$ \Theta(n)
$ \mathtt{peek}()
ヒープの最小の要素を返す
時間計算量$ \Theta(1)
$ \mathtt{pop}()
ヒープの最小の要素を削除して返す
時間計算量$ \Omicron(\log n)
$ \mathtt{insert}(x)
ヒープに要素$ xを追加する
時間計算量$ \Omicron(\log n) (動的配列を用いた典型的な実装では amortized)
Summary
https://gyazo.com/a479e15c335fbfd4892324c228cd717d
各ノードに要素を乗せた完全二分木．子の要素はつねに親の要素と等しいかより大きいという不変条件 (heap property) を保つ．heap property より，根の要素が最小となることが従う．
https://gyazo.com/9a3b2b0cf043b4b37dbb1e2631ea4d38
この完全二分木は配列で管理されることが多い．
$ \mathtt{pop}
https://gyazo.com/d56927bbe7667f424c914217b08e5fee
根を末端ノードと swap して取り出した後，その (新しく根となった) ノードを heap property を満たすまで子と繰り返し swap する (down-heap)．
$ \mathtt{insert}
https://gyazo.com/334e2184c713d823841246858dac7b05
まず末端に新しい要素のノードを追加し，heap property を満たすまで親と swap することを繰り返す (up-heap)．