ALDS1_9_C: Priority Queue
二分ヒープに挿入と取り出しをつけて優先度キューに仕立て上げようという問題
今回は問題文にアルゴリズムの説明はない
ということは、これまでのアルゴリズムを再利用するということかな?
それとも説明するほど難しくはないということ?
一番単純な再利用は毎回build_max_heapを実行することだけど
それではオーダがn^2 になってしまうし
まずは挿入から考えてみよう
max_heapifyだけ使うってことはできるかな
一番上(つまり配列の先頭)に挿入して一番上からmax_heapifyとか
一番上に挿入したとき、下位が二分ヒープの構造をキープしてるかって言うと
してない気がする
そうすると再利用はできないってことかなあ
既存の二分ヒープの構造を崩さないように要素を挿入するなら末尾
そこから適当な場所まで持ち上げていく感じ?
max_heapifyと似たようなコードで書けるかな?
取り出しはどうかな
取り出しはちょっとややこしいような気がするけど・・・
もしかして先頭を削除しても二分ヒープの形は残るとかあるかな?
うーんやっぱないなあ
やっぱり末尾から持ち上げていく感じ?