Overview
ヒープソート（Heap Sort） は、ヒープ（Heap）を利用して $O(N log N)$で動作するソートアルゴリズム 。ヒープを使って最大（または最小）値を取り出しながら配列をソートする。
1.ヒープソートの基本概念
2.ヒープソートのアルゴリズム
3.ヒープソートの応用
4.典型問題を解いてみる
1. ヒープソートの基本概念
ヒープソートは以下の2つのステップで構成される：
1. 配列をヒープ（完全二分木）に変換
2. ヒープの最大（または最小）値を取り出して、ソートを完了させる
(1) ヒープソートの特徴
-
計算量：$O(N log N)$
ヒープの構築($O(N）$) + ヒープ操作($O(log N)$を N 回） -
安定性：非安定ソート
同じ値の要素が、元の順番と異なる順番で出力される可能性がある -
メモリ使用量：$O(1)$（配列内での操作のみ）
追加の配列を使わず、内部でヒープ操作を行う -
最悪計算量 $O(N log N)$ を保証
クイックソート（Quick Sort）は最悪 $O(N^2)$ の可能性があるが、ヒープソートは $O(N log N)$ で安定
2. ヒープソートのアルゴリズム
(1) 配列をヒープに変換（Heapify）
- 完全二分木の形を作り、最大ヒープ（または最小ヒープ）を構築
- 子ノードが親ノードより大きくならないように調整
- ヒープ構築の計算量：$O(N)$
def heapify(arr, n, i):
largest = i # 親ノード
left = 2 * i + 1 # 左の子
right = 2 * i + 2 # 右の子
# 左の子が親より大きければ更新
if left < n and arr[left] > arr[largest]:
largest = left
# 右の子が親より大きければ更新
if right < n and arr[right] > arr[largest]:
largest = right
# 親ノードが最大でない場合、交換して再帰的に調整
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
(2) ヒープソートの実装
- ヒープを構築した後、ルート（最大値）を取り出して整列
- ヒープサイズを縮小しながら、残りの部分を再調整
def heap_sort(arr):
n = len(arr)
# 1. 配列をヒープ化（最大ヒープを作成）
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 2. ヒープの最大要素を取り出し、配列末尾と交換しながらソート
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 最大値を末尾に移動
heapify(arr, i, 0) # 残りのヒープを調整
# 使用例
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr) # 出力: [1, 3, 4, 5, 10]
- 計算量: O(N log N)
- ヒープ構築：O(N)
- ヒープから要素を削除して再構築：O(log N) を N 回実行 → O(N log N)
3. ヒープソートの応用
(1) K 番目に小さい要素を求める
ヒープを使えば、配列内の K 番目の最小値を効率的に取得 できる。
import heapq
arr = [7, 10, 4, 3, 20, 15]
k = 3
heapq.heapify(arr) # ヒープ化
for _ in range(k - 1):
heapq.heappop(arr) # k-1 回最小値を取り出す
print(heapq.heappop(arr)) # 3番目に小さい値（7）
- O(N + K log N) で求められる
(2) 大量データのソート
- 通常のソートより、O(N log N) で安定した性能を発揮
- 追加メモリを使用しないため、大規模データに向いている
4. 典型問題を解いてみる
例題1. ヒープソートの実装
問題: N 個の整数をヒープソートでソートせよ。
回答
N = int(input())
arr = list(map(int, input().split()))
heap_sort(arr)
print(*arr)
例題2. K 番目に小さい要素を求める
問題: N 個の整数 A から K 番目に小さい値を求めよ。
回答
import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(K - 1):
heapq.heappop(A)
print(heapq.heappop(A))
例題3. 優先度付きキューのシミュレーション
問題: N 個のクエリが与えられる。insert x で x を追加し、pop で最小値を取り出せ。
回答
import heapq
N = int(input())
heap = []
for _ in range(N):
query = input().split()
if query[0] == "insert":
heapq.heappush(heap, int(query[1]))
elif query[0] == "pop":
print(heapq.heappop(heap))