概要
概要
二分ヒープを使って最大値を何度も末尾へ送ります。比較的安定した O(n log n) ですが、安定ソートではありません。
ソート / Heap Sort（ヒープソート）
二分ヒープを使って最大値を何度も末尾へ送ります。比較的安定した O(n log n) ですが、安定ソートではありません。
目次
このページでわかること
概要
二分ヒープを使って最大値を何度も末尾へ送ります。比較的安定した O(n log n) ですが、安定ソートではありません。
考え方
build max heap
swap root with last element
shrink heap
heapify root要点
O(n log n)
O(n log n)
O(n log n)
いいえ
補足
まずヒープを作り、その後 root を取り出して再ヒープ化します。
木と配列の対応を並べると理解しやすいです。
最悪時も O(n log n) を保ちます。
動きで確認
ここでは「完全二分木として考える」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。