kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_9_C: Priority Queue

二分ヒープに挿入と取り出しをつけて優先度キューに仕立て上げようという問題
今回は問題文にアルゴリズムの説明はない

ということは、これまでのアルゴリズムを再利用するということかな?
それとも説明するほど難しくはないということ?

一番単純な再利用は毎回build_max_heapを実行することだけど
それではオーダがn^2 になってしまうし

まずは挿入から考えてみよう
max_heapifyだけ使うってことはできるかな
一番上(つまり配列の先頭)に挿入して一番上からmax_heapifyとか
一番上に挿入したとき、下位が二分ヒープの構造をキープしてるかって言うと
してない気がする

そうすると再利用はできないってことかなあ

既存の二分ヒープの構造を崩さないように要素を挿入するなら末尾
そこから適当な場所まで持ち上げていく感じ?
max_heapifyと似たようなコードで書けるかな?

取り出しはどうかな
取り出しはちょっとややこしいような気がするけど・・・
もしかして先頭を削除しても二分ヒープの形は残るとかあるかな?
うーんやっぱないなあ
やっぱり末尾から持ち上げていく感じ?